𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Approximating Rooted Connectivity Augmentation Problems

✍ Scribed by Zeev Nutov

Publisher
Springer
Year
2005
Tongue
English
Weight
246 KB
Volume
44
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

Two-Connected Augmentation Problems in P
Two-Connected Augmentation Problems in Planar Graphs
✍ J.Scott Provan; Roger C Burk πŸ“‚ Article πŸ“… 1999 πŸ› Elsevier Science 🌐 English βš– 167 KB

Given a weighted undirected graph G and a subgraph S of G, we consider the problem of adding a minimum-weight set of edges of G to S so that the resulting Ε½ . subgraph satisfies specified edge or vertex connectivity requirements between pairs of nodes of S. This has important applications in upgradi