TY - JOUR

T1 - Improved Approximation Algorithms for Uniform Connectivity Problems

AU - Khuller, Samir

AU - Raghavachari, Balaji

N1 - Funding Information:
* A preliminary draft of this paper appeared in the ``Proceedings of the 27th Annual ACM Symposium on Theory of Computing STOC), 1995.'' ²Research supported by NSF Research Initiation Award CCR-9307462 and an NSF CAREER Award CCR-9501355. E-mail: samir@cs.umd.edu. ³Research supported in part by NSF Research Initiation Award CCR-9409625. E-mail: rbk@utdallas.edu.

PY - 1996/9

Y1 - 1996/9

N2 - The problem of finding minimum-weight spanning subgraphs with a given connectivity requirement is considered. The problem is NP-hard when the connectivity requirement is greater than one. Polynomial time approximation algorithms for various weighted and unweighted connectivity problems are given. The following results are presented: 1. For the unweighted k-edge-connectivity problem an approximation algorithm that achieves a performance ratio of 1.85 is described. This is the first polynomial-time algorithm that achieves a constant less than 2, for all k. 2. For the weighted k-vertex-connectivity problem, a constant factor approximation algorithm is given assuming that the edge-weights satisfy the triangle inequality. This is the first constant factor approximation algorithm for this problem. 3. For the case of biconnectivity, with no assumptions about the weights of the edges, an algorithm that achieves a factor asymptotically approaching 2 is described. This matches the previous best bound for the corresponding edge connectivity problem.

AB - The problem of finding minimum-weight spanning subgraphs with a given connectivity requirement is considered. The problem is NP-hard when the connectivity requirement is greater than one. Polynomial time approximation algorithms for various weighted and unweighted connectivity problems are given. The following results are presented: 1. For the unweighted k-edge-connectivity problem an approximation algorithm that achieves a performance ratio of 1.85 is described. This is the first polynomial-time algorithm that achieves a constant less than 2, for all k. 2. For the weighted k-vertex-connectivity problem, a constant factor approximation algorithm is given assuming that the edge-weights satisfy the triangle inequality. This is the first constant factor approximation algorithm for this problem. 3. For the case of biconnectivity, with no assumptions about the weights of the edges, an algorithm that achieves a factor asymptotically approaching 2 is described. This matches the previous best bound for the corresponding edge connectivity problem.

UR - http://www.scopus.com/inward/record.url?scp=0030367201&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0030367201&partnerID=8YFLogxK

U2 - 10.1006/jagm.1996.0052

DO - 10.1006/jagm.1996.0052

M3 - Article

AN - SCOPUS:0030367201

VL - 21

SP - 434

EP - 450

JO - Journal of Algorithms

JF - Journal of Algorithms

SN - 0196-6774

IS - 2

ER -