Paper Info
Title
Minimum Augmentation of Edge-Connectivity between Vertices and Sets of Vertices in Undirected Graphs
Abstract
Given an undirected multigraph G = ( V , E ), a family W of areas W ⊆ V , and a target connectivity k ≥ 1, we consider the problem of augmenting G by the smallest number of new edges so that the resulting graph has at least k edge-disjoint paths between μ and W for every pair of a vertex μ ∈ V and an area W ∈ W . So far this problem was shown to be NP-complete in the case of k = 1. and polynomially solvable in the case of k = 2. In this paper, we show that the problem for k ≥ 3 can be solved in O ( m + n ( k 3 + n 2 )( p + kn + n log n ) log k + pkn 3 log( n / k )) time, where n = ∣V∣, m = ∣{{u,v}∣(u, v) ∈ E}∣, and p = ∣ W ∣ .
Year
DOI
Venue
2010
10.1016/S1571-0661(04)81016-8
Electronic Notes in Theoretical Computer Science
Keywords
DocType
Volume
undirected graph · connectivity augmentation problem · edge-connectivity · node-to-area connectivity · polynomial time deterministic algorithm · edge-splitting
Journal
56
Issue
ISSN
Citations 
4
Electronic Notes in Theoretical Computer Science
4
PageRank 
References 
Authors
0.59
11
3
Name
Order
Citations
PageRank
Toshimasa Ishii111017.03
Yoko Akiyama282.35
Hiroshi Nagamochi31513174.40