## Tree Embeddings for Two-Edge-Connected Network Design

journal contribution

posted on 01.05.2005 by Anupam Gupta, Ravishankar Krishnaswamy, Ramamoorthi Ravi#### journal contribution

Any type of content formally published in an academic journal, usually following a peer-review process.

The group Steiner problem is a classical network design
problem where we 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 we 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 we 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?
In this paper, we investigate tree-embedding techniques that can be used to solve these and other 2-edge-connected network design problems. We illustrate the
potential of these techniques by giving poly-logarithmic
approximation algorithms for two-edge-connected versions of the group Steiner, connected facility location,
buy-at-bulk, and the k-MST problems.