✦ LIBER ✦

NOTE Improved Approximation Algorithms for Weighted 2- and 3-Vertex Connectivity Augmentation Problems

✍ Scribed by Michal Penn; Haya Shasha-Krupnik

Publisher: Elsevier Science
Year: 1997
Tongue: English
Weight: 126 KB
Volume: 22
Category: Article
ISSN: 0196-6774
DOI: 10.1006/jagm.1995.0800

No coin nor oath required. For personal study only.

✦ Synopsis

The problem of finding a minimum augmenting edge-set to make a graph k-vertex connected is considered. This problem is denoted as the minimum k-augmentation problem. For weighted graphs, the minimum k-augmentation problem is NP-complete. Our main result is an approximation algorithm with a performance ratio of 3 for solving the minimum 3-augmentation problem. This improves the best previously known performance guarantee of 11r3. We also have the following marginal result: an approximation algorithm for the minimum 2-augmentation problem that achieves a factor of 2, and thus improves the previously known factor Ž . of 2 q 1rn , with n as the number of vertices in the graph.

📜 SIMILAR VOLUMES

A Static 2-Approximation Algorithm for V

A Static 2-Approximation Algorithm for Vertex Connectivity and Incremental Approximation Algorithms for Edge and Vertex Connectivity

✍ Monika Rauch Henzinger 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 329 KB

This paper presents insertions-only algorithms for maintaining the exact andror approximate size of the minimum edge cut and the minimum vertex cut of a graph. Ž . The algorithms output the approximate or exact size k in time O 1 and a cut of size k in time linear in its size. For the minimum edge

A 2-Approximation Algorithm for Finding

A 2-Approximation Algorithm for Finding an Optimum 3-Vertex-Connected Spanning Subgraph

✍ Vincenzo Auletta; Yefim Dinitz; Zeev Nutov; Domenico Parente 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 71 KB

The problem of finding a minimum weight k-vertex connected spanning sub-Ž . graph in a graph G s V, E is considered. For k G 2, this problem is known to be NP-hard. Combining properties of inclusion-minimal k-vertex connected graphs Ž and of k-out-connected graphs i.e., graphs which contain a vertex