Back to Search
Start Over
A CONSTANT FACTOR APPROXIMATION FOR MINIMUM λ-EDGE-CONNECTED k-SUBGRAPH WITH METRIC COSTS.
- Source :
- SIAM Journal on Discrete Mathematics; 2011, Vol. 25 Issue 3/4, p1089-1102, 14p, 2 Diagrams, 2 Charts
- Publication Year :
- 2011
-
Abstract
- In the (k, λ)-subgraph problem, we are given an undirected graph G = (V, E) with edge costs and two positive integers k and λ, and the goal is to find a minimum cost simple λ-edge-connected subgraph of G with at least k nodes. This generalizes several classical problems, such as the minimum cost k-spanning tree problem, or k-MST (which is a (k, 1)-subgraph), and the minimum cost λ-edge-connected spanning subgraph (which is a (|V(G)|, λ-subgraph). The only previously known results on this problem [L. C. Lau, J. S. Naor, M. R. Salavatipour, and M. Singh, SIAM J. Comput., 39 (2009), pp. 1062-1087], [C. Chekuri and N. Korula, in Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), Bangalore, India, LIPIcs 2, Schloss Dagstuhl--Leibniz-Zentrum für Informatik, Dagstuhl, Germany, 2008, pp. 119-130] show that the (k, 2)-subgraph problem has an O(log² n)-approximation (even for 2-node-connectivity) and that the (k, λ)-subgraph problem in general is almost as hard as the densest k-subgraph problem. In this paper we show that if the edge costs are metric (i.e., satisfy the triangle in equality), like in the k-MST problem, then there is an O(1)-approximation algorithm for the (k, λ)-subgraph problem. This essentially generalizes the k-MST constant factor approximability to higher connectivity. [ABSTRACT FROM AUTHOR]
- Subjects :
- ALGORITHMS
GRAPHIC methods
COMBINATORIAL optimization
MATHEMATICS
COST
Subjects
Details
- Language :
- English
- ISSN :
- 08954801
- Volume :
- 25
- Issue :
- 3/4
- Database :
- Complementary Index
- Journal :
- SIAM Journal on Discrete Mathematics
- Publication Type :
- Academic Journal
- Accession number :
- 71525582
- Full Text :
- https://doi.org/10.1137/080729918