Minimum Augmentation of Edge-Connectivity between Vertices and Sets of Vertices in Undirected Graphs

摘要

Given an undirected multigraph G=(V,E), a family 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 v and W for every pair of a vertex v∈V and an area . 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+nlog n)log k+pkn 3log (n/k)) time, where n=|V|, m=|{{u,v}|(u,v)∈E}|, and . Keywords Undirected graph - Connectivity augmentation problem - Edge-connectivity - Node-to-area connectivity - Polynomial time deterministic algorithm - Edge-splitting An extended abstract of this paper was presented at 9th Computing: The Australasian Theory Symposium (CATS 2003), Australia, February 2003.