Improved Approximation Algorthmsor Uniform Connectivity Problems

Loading...
Thumbnail Image

Files

CS-TR-3418.ps (180.5 KB)
No. of downloads: 202
CS-TR-3418.pdf (195.42 KB)
No. of downloads: 618

Publication or External Link

Date

1998-10-15

Advisor

Citation

DRUM DOI

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 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. (Also cross-referenced as UMIACS-TR-95-21)

Notes

Rights