Improved Approximation Algorthmsor Uniform Connectivity Problems
Files
Publication or External Link
Date
Authors
Advisor
Citation
DRUM DOI
Abstract
The problem of finding minimum weight spanning subgraphs with a given connectivity requirement is considered. The problem is NPhard 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:

For the unweighted kedgeconnectivity problem an approximation algorithm that achieves a performance ratio of 1.85 is described. This is the first polynomialtime algorithm that achieves a constant less than 2, for all k.

For the weighted vertexconnectivity problem, a constant factor approximation algorithm is given assuming that the edgeweights satisfy the triangle inequality. This is the first constant factor approximation algorithm for this problem.

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 crossreferenced as UMIACSTR9521)