Improved Approximation Algorthmsor Uniform Connectivity Problems

dc.contributor.authorKhuller, Samiren_US
dc.contributor.authorRaghavachari, Balajien_US
dc.date.accessioned2004-05-31T22:30:27Z
dc.date.available2004-05-31T22:30:27Z
dc.date.created1995-02en_US
dc.date.issued1998-10-15en_US
dc.description.abstractThe 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)en_US
dc.format.extent184828 bytes
dc.format.mimetypeapplication/postscript
dc.identifier.urihttp://hdl.handle.net/1903/700
dc.language.isoen_US
dc.relation.isAvailableAtDigital Repository at the University of Marylanden_US
dc.relation.isAvailableAtUniversity of Maryland (College Park, Md.)en_US
dc.relation.isAvailableAtTech Reports in Computer Science and Engineeringen_US
dc.relation.isAvailableAtUMIACS Technical Reportsen_US
dc.relation.ispartofseriesUM Computer Science Department; CS-TR-3418en_US
dc.relation.ispartofseriesUMIACS; UMIACS-TR-95-21en_US
dc.titleImproved Approximation Algorthmsor Uniform Connectivity Problemsen_US
dc.typeTechnical Reporten_US

Files

Original bundle
Now showing 1 - 2 of 2
No Thumbnail Available
Name:
CS-TR-3418.ps
Size:
180.5 KB
Format:
Postscript Files
Loading...
Thumbnail Image
Name:
CS-TR-3418.pdf
Size:
195.42 KB
Format:
Adobe Portable Document Format
Description:
Auto-generated copy of CS-TR-3418.ps