Multigraph augmentation under biconnectivity and general edge‐connectivity requirements
Toshimasa Ishii, Hiroshi Nagamochi, Toshihide Ibaraki · Networks · 2001
Abstract Given an undirected multigraphG= (V,E) and a requirement functionrλ: ( ) →Z+(where ( ) is the set of all pairs of vertices andZ+is the set of nonnegative integers), we consider the problem of augmentingGby the smallest number of new edges so that the local edge‐connectivity and vertex‐connectivity between every pairx,y∈Vbecome at leastrλ(x,y) and two, respectively. In this paper, we show that the problem can be solved inO(n3(m+n) log(n2/(m+n))) time, wherenandmare the numbers of vertices and pairs of adjacent vertices inG, respectively. This time complexity can be improved toO((nm+n2logn) logn), in the case of the uniform requirementrλ(x,y)= 𝓁 for allx,y∈V. Furthermore, for the generalrλ, we show that the augmentation problem that preserves the simplicity of the resulting graph can be solved in polynomial time for any fixed 𝓁*= max{rλ(x,y) |x,y∈V}. © 2001 John Wiley & Sons, Inc.