𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On the minimum local-vertex-connectivity augmentation in graphs

✍ Scribed by Hiroshi Nagamochi; Toshimasa Ishii

Publisher
Elsevier Science
Year
2003
Tongue
English
Weight
179 KB
Volume
129
Category
Article
ISSN
0166-218X

No coin nor oath required. For personal study only.

✦ Synopsis

Given a graph G and target values r(u; v) prescribed for each pair of vertices u and v, we consider the problem of augmenting G by a smallest set F of new edges such that the resulting graph G+F has at least r(u; v) internally disjoint paths between each pair of vertices u and v. We show that the problem is NP-hard even if for some constant k ¿ 2 G is (k -1)-vertex-connected and r(u; v) ∈ {0; k} holds for u; v ∈ V . We then give a linear time algorithm which delivers a 3 2 -approximation solution to the problem with a connected graph G and r(u; v) ∈ {0; 2}, u; v ∈ V .

πŸ“œ SIMILAR VOLUMES

On the Edge Connectivity, Hamiltonicity,
On the Edge Connectivity, Hamiltonicity, and Toughness of Vertex-Transitive Graphs
✍ Jan van den Heuvel; Bill Jackson πŸ“‚ Article πŸ“… 1999 πŸ› Elsevier Science 🌐 English βš– 191 KB

Let G be a connected k-regular vertex-transitive graph on n vertices. For S V(G) let d(S) denote the number of edges between S and V(G)"S. We extend results of Mader and Tindell by showing that if d(S)< 2 9 (k+1) 2 for some S V(G) with 1 3 (k+1) |S| 1 2 n, then G has a factor F such that GΓ‚E(F ) is