Multigraph augmentation under biconnectivity and general edge-connectivityrequirements

Given an undirected multigraph G =(V, E) and a requirement function r(lambd a): ((V)(2)) --> Z(+) (where ((V)(2)) is the set of all pairs of vertices a nd Z+ is the set of nonnegative integers), we consider the problem of augme nting G by the smallest number of new edges so that the local edge-connecti vity and vertex-connectivity between every pair x, y is an element of V bec ome at least r(lambda) (x, y) and two, respectively. In this paper, we show that the problem can be solved in O(n(3)(m + n) log(n(2)/(m + n))) time, w here n and m are the numbers of vertices and pairs of adjacent vertices in G, respectively. This time complexity can be improved to O((nm + n? log n) log n), in the case of the uniform requirement r lambda (x, y) = l for all x, y is an element of V. Furthermore, for the general r(lambda), we show th at the augmentation problem that preserves the simplicity of the resulting graph can be solved in polynomial time for any fixed l* = max{r lambda (x, y) \ x, y is an element of V}. (C) 2001 John Wiley & Sons, Inc.