Security

Tree Embeddings for Two-Edge-Connected Network Design

Date Added: Oct 2009
Format: PDF

The group Steiner problem is a classical network design problem where the authors are given a graph and a collection of groups of vertices, and want to build a min-cost subgraph that connects the root vertex to at least one vertex from each group. What if they wanted to build a subgraph that two-edge-connects the root to each group that is, for every group g ? V, the subgraph should contain two edge-disjoint paths from the root to some vertex in g? What if the authors wanted the two edge-disjoint paths to end up at distinct vertices in the group, so that the loss of a single member of the group would not destroy connectivity?