Connectivity Augmentation
Hiroshi Nagamochi, Toshihide Ibaraki · Cambridge University Press eBooks · 2008
The problem of increasing edge or vertex-connectivity of a given graph up to a specified target value k by adding the smallest number of new edges is called connectivity augmentation . These problems were first studied in 1976 by Eswaran and Tarjan [64] and Plesnik [275] and were shown to be polynomially solvable for k = 2. The problems have important applications such as the network construction problem [279], the rigidity problem in grid frameworks [13, 99], the data security problem [110, 172], and the rectangular dual graph problem in floor planning [303]. We refer to [81, 241] surveys for this study. In this chapter, we mainly treat the edge-connectivity augmentation problem for a given target value k . For a general k , Watanabe and Nakamura [308] established in 1987 a min-max theorem, based on which they gave an O ( k 2 ( kn + m ) n 4 ) time algorithm. Afterward, Frank [78] gave a unified approach to various edgeconnectivity augmentation problems by making use of the edge-splitting theorems of Lovász [200, 202] and Mader [206, 208]. Then Nagamochi and Ibaraki [236] proposed an O (( nm + n 2 log n ) log n ) time algorithm by combining the minimumcut algorithm in Section 3.2 and the approach of Frank. If the graph under consideration is weighted by real numbers, this algorithm can be further simplified and can be extended to solve the edge-connectivity augmentation problem for the entire range of target k in O ( nm + n 2 log n ) time [238], as will be explained in Section 8.4. By using extreme vertex sets in Section 1.5.3, Benczúr and Karger [20] gave an O ( n 2 log 5 n ) time randomized algorithm of Monte Carlo type to optimally increase a multigraph.