𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Hardness of Approximation for Vertex-Connectivity Network Design Problems

✍ Scribed by Kortsarz, Guy; Krauthgamer, Robert; Lee, James R.

Book ID
118181207
Publisher
Society for Industrial and Applied Mathematics
Year
2004
Tongue
English
Weight
240 KB
Volume
33
Category
Article
ISSN
0097-5397

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

Approximation Algorithms for Network Des
Approximation Algorithms for Network Design Problems on Bounded Subsets
✍ Dorit S. Hochbaum; Joseph (Seffi) Naor πŸ“‚ Article πŸ“… 1996 πŸ› Elsevier Science 🌐 English βš– 141 KB

We address the problem of designing a network so that certain connectivity requirements are satisfied, at minimum cost of the edges used. The requirements are specified for each subset of vertices in terms of the number of edges with one endpoint in the set. We address a class of such problems, wher