✦ LIBER ✦

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

✍ Scribed by Vincenzo Auletta; Yefim Dinitz; Zeev Nutov; Domenico Parente

Publisher: Elsevier Science
Year: 1999
Tongue: English
Weight: 71 KB
Volume: 32
Category: Article
ISSN: 0196-6774
DOI: 10.1006/jagm.1999.1006

No coin nor oath required. For personal study only.

✦ Synopsis

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 from which . there exist k internally vertex-disjoint paths to every other vertex , we derive Ž . polynomial time algorithm for finding a kr2 q 1 -connected subgraph with a u v weight at most twice the optimum to the original problem. In particular, we obtain * Corresponding author. † This work was done as a part of the author's D.Sc. thesis at the Dept. of Mathematics,

📜 SIMILAR VOLUMES

A 3-Approximation Algorithm for Finding

A 3-Approximation Algorithm for Finding Optimum 4,5-Vertex-Connected Spanning Subgraphs

✍ Yefim Dinitz; Zeev Nutov 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 103 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. Based on the paper of Auletta, Dinitz, Nutov, and Parente in this issue, Ä 4 we derive a 3-approximation algorithm for k g 4, 5 . This

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

NOTE Improved Approximation Algorithms f

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

✍ Michal Penn; Haya Shasha-Krupnik 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 126 KB

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 performan