max planck institut

informatik

informatik

<< Previous Entry | Next Entry >> | New Event Entry | Edit this Entry | Login to DB (to update, delete) |

Title: | Beyond Metric Embedding: Approximating Group Steiner Trees on Bounded Treewidth Graphs |
---|---|

Speaker: | Daniel Vaz |

coming from: | Max-Planck-Institut für Informatik - D1 |

Speakers Bio: | |

Event Type: | AG1 Mittagsseminar (own work) |

Visibility: | D1 We use this to send out email in the morning. |

Level: | AG Audience |

Language: | English |

Date: | Thursday, 5 January 2017 |
---|---|

Time: | 13:00 |

Duration: | 30 Minutes |

Location: | Saarbrücken |

Building: | E1 4 - MPI-INF |

Room: | 024 |

The Group Steiner Tree (GST) problem is a classical problem in combinatorial optimization and theoretical computer science. In the Edge-Weighted Group Steiner Tree (EW-GST) problem, we are given an undirected graph G=(V,E) on n vertices with edge costs c, a source vertex s and a collection of subsets of vertices, called groups, S_1, ..., S_k (subsets of V). The goal is to find a minimum-cost tree H that connects s to some vertex from each group S_i, for all i = 1, 2, ..., k. The Node-Weighted Group Steiner Tree (NW-GST) problem has the same setting, but the costs are associated with nodes. The goal is to find a minimum-cost node set X such that G[X] connects every group to the source. |

Name(s): | Daniel Vaz |
---|---|

EMail: | ramosvaz@mpi-inf.mpg.de |

Video Broadcast: | No | To Location: |
---|

Note: | |
---|---|

Attachments, File(s): |

Created: | Daniel Vaz, 11/29/2016 03:28 PM |

Last modified: | Uwe Brahm/MPII/DE, 01/05/2017 04:01 AM |

- Daniel Vaz, 12/01/2016 02:03 PM
- Daniel Vaz, 11/29/2016 03:28 PM -- Created document.