著者

永持 仁

出版者

一般社団法人日本応用数理学会

雑誌

応用数理 (ISSN:09172270)

巻号頁・発行日

vol.8, no.1, pp.20-29, 1998-03-16

---

The connectivity augmentation problem asks to add to a given graph the smallest number of new edges so that the edge- (or vertex-) connectivity of the graph increases up to a specified value k. The problem is first studied by K. P. Eswaran and R. E. Tarjan in 1976, and both type of connectivity augmentation problems for k=2 are shown to be polynomially solvable. Afterwards, in 1987 T. Watanabe and A. Nakamura proved that the problem of making a given graph k-edge-connected by adding the smallest number of edges can be solved in O(k^2(kn+m)n^4) time for general k, where n and m are the number of vertices and edges in the input graph, respectively. Recently, a significantly faster O(nm log n+n^2 log^2 n) time algorithm for solving this problem is proposed by H. Nagamochi and T. Ibaraki by applying L. Lovasz's edge-splitting theorem. This note first reviews this alogorithm and then shows how to modify the algorithm to solve the edgeconnectivity augmentation problem for a graph with real-weighted edges.