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

作者：Ishii Toshimasa^*; Akiyama Yoko; Nagamochi Hiroshi

来源：Algorithmica, 2010, 56(4): 413-436.

DOI：10.1007/s00453-008-9178-y

• Undirected graph
• Connectivity augmentation problem
• Edge-connectivity
• Node-to-area connectivity
• Polynomial time deterministic algorithm
• Edge-splitting

Given an undirected multigraph G = (V, E), a familyW of areas W subset of 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 is an element of V and an area W is an element of 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 = vertical bar V vertical bar, m = vertical bar{{u, v}vertical bar(u, v) is an element of E}vertical bar, and p = vertical bar W vertical bar.

• 出版日期2010-4