Tree embeddings for two-edge-connected network design

Anupam Gupta, Ravishankar Krishnaswamy, R. Ravi

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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.

Original languageEnglish (US)
Title of host publicationProceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms
PublisherAssociation for Computing Machinery (ACM)
Number of pages18
ISBN (Print)9780898717013
StatePublished - 2010
Event21st Annual ACM-SIAM Symposium on Discrete Algorithms - Austin, TX, United States
Duration: Jan 17 2010Jan 19 2010

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms


Other21st Annual ACM-SIAM Symposium on Discrete Algorithms
Country/TerritoryUnited States
CityAustin, TX

ASJC Scopus subject areas

  • Software
  • General Mathematics


Dive into the research topics of 'Tree embeddings for two-edge-connected network design'. Together they form a unique fingerprint.

Cite this