Improved Approximation Algorithms for Uniform Connectivity Problems

Samir Khuller*, Balaji Raghavachari

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

108 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages (from-to)434-450
Number of pages17
JournalJournal of Algorithms
Volume21
Issue number2
DOIs
StatePublished - Sep 1996

ASJC Scopus subject areas

  • Control and Optimization
  • Computational Mathematics
  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'Improved Approximation Algorithms for Uniform Connectivity Problems'. Together they form a unique fingerprint.

Cite this