@article{oai:barrel.repo.nii.ac.jp:00002613,
author = {Ishii, Toshimasa and Akiyama, Yoko and Nagamochi, Hiroshi},
journal = {Algorithmica},
month = {Mar},
note = {Given an undirected multigraph G=(V,E), a family $\mathcal{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 v and W for every pair of a vertex v∈V and an area $W\in \mathcal{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+nlog n)log k+pkn 3log (n/k)) time, where n=|V|, m=|{{u,v}|(u,v)∈E}|, and $p=|\mathcal{W}|$},
title = {Minimum augmentation of edge-connectivity between vertices and sets of vertices in undirected graphs},
year = {2008}
}