𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Kernelization and complexity results for connectivity augmentation problems

✍ Scribed by Jiong Guo; Johannes Uhlmann

Publisher
John Wiley and Sons
Year
2009
Tongue
English
Weight
246 KB
Volume
56
Category
Article
ISSN
0028-3045

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

Pushdown–reduce: an algorithm for connec
Pushdown–reduce: an algorithm for connectivity augmentation and poset covering problems
✍ AndrΓ‘s A. BenczΓΊr πŸ“‚ Article πŸ“… 2003 πŸ› Elsevier Science 🌐 English βš– 557 KB

In their seminal paper, Frank and Jordà an show that a large class of optimization problems including certain directed edge augmentation ones fall into the class of covering supermodular functions over pairs of sets. They also give an algorithm for such problems, however, that relies on the ellipsoi

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

Fast Algorithms for k-Shredders and k-No
Fast Algorithms for k-Shredders and k-Node Connectivity Augmentation
✍ Joseph Cheriyan; Ramakrishna Thurimella πŸ“‚ Article πŸ“… 1999 πŸ› Elsevier Science 🌐 English βš– 321 KB

A k-separator k-shredder of a k-node connected undirected graph is a set of k Ε½ . nodes whose removal results in two or more three or more connected components. Let n denote the number of nodes. Solving an open question, we show that the problem of counting the number of k-separators is ΰ »P-complete.