DocumentCode :
1594026
Title :
Algorithms for Single-Source Vertex Connectivity
Author :
Chuzhoy, Julia ; Khanna, Sanjeev
Author_Institution :
Toyota Technol. Inst., Chicago, IL
fYear :
2008
Firstpage :
105
Lastpage :
114
Abstract :
In the survivable network design problem (SNDP) the goal is to find a minimum cost subset of edges that satisfies a given set of pairwise connectivity requirements among the vertices. This general network design framework has been studied extensively and is tied to the development of major algorithmic techniques. For the edge-connectivity version of the problem, a 2-approximation algorithm is known for arbitrary pairwise connectivity requirements. However, no non-trivial algorithms are known for its vertex connectivity counterpart. In fact, even highly restricted special cases of the vertex connectivity version remain poorly understood.We study the single-source k-vertex connectivity version of SNDP. We are given a graph G(V,E) with a subset T of terminals and a source vertex s, and the goal is to find a minimum cost subset of edges ensuring that every terminal is k-vertex connected to s. Our main result is an O(k log n)-approximation algorithm for this problem; this improves upon the recent 2O(k 2 )log4 n-approximation. Our algorithm is based on an intuitive rerouting scheme. The analysis relies on a structural result that may be of independent interest: we show that any solution can be decomposed into a disjoint collection of multiple-legged spiders, which are then used to re-route flow from terminals to the source via other terminals.We also obtain the first non-trivial approximation algorithm for the vertex-cost version of the same problem, achieving an O(k7log2 n)-approximation.
Keywords :
approximation theory; computational complexity; graph theory; network theory (graphs); set theory; 2-approximation algorithm; O(k log n)-approximation algorithm; edge-connectivity version; graph; intuitive rerouting scheme; minimum cost subset; multiple-legged spiders; nontrivial approximation algorithm; single-source vertex connectivity; survivable network design problem; vertex-cost version; Algorithm design and analysis; Approximation algorithms; Computer science; Costs; Iterative algorithms; Joining processes; Polynomials; Tree graphs; Network Design; Vertex Connectivity;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Foundations of Computer Science, 2008. FOCS '08. IEEE 49th Annual IEEE Symposium on
Conference_Location :
Philadelphia, PA
ISSN :
0272-5428
Print_ISBN :
978-0-7695-3436-7
Type :
conf
DOI :
10.1109/FOCS.2008.63
Filename :
4690945
Link To Document :
بازگشت