𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Polynomial Time Algorithms for 2-Edge-Connectivity Augmentation Problems

✍ Scribed by Anna Galluccio and Guido Proietti

Book ID
120136600
Publisher
Springer
Year
2003
Tongue
English
Weight
118 KB
Volume
36
Category
Article
ISSN
0178-4617

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

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

Augmenting Undirected Edge Connectivity
Augmenting Undirected Edge Connectivity in Γ•(n2) Time
✍ AndrΓ‘s A BenczΓΊr; David R Karger πŸ“‚ Article πŸ“… 2000 πŸ› Elsevier Science 🌐 English βš– 218 KB

We give improved randomized Monte Carlo algorithms for undirected edge splitting and edge connectivity augmentation problems. Our algorithms run in time ˜2 Ε½ . Ε½ . O n on n-vertex graphs, making them an ⍀ mrn factor faster than the best known deterministic ones on m-edge graphs.