ON THE OPTIMAL VERTEX-CONNECTIVITY AUGMENTATION

This paper considers the problem of finding a minimum-cardinality set of edges for a given k-connected graph whose addition makes it (k+1)-connected. We give sharp lower and upper bounds for this minimum, where the gap between them is at most k-2. This result is a generalization of the solved cases k=1, 2, where the exact min-max formula is known. We present a polynomial-time approximation algorithm which makes a k-connected graph (k+1)-connected by adding a new set of edges with size at most k-2 over the optimum. (C) 1995 Academic Press, Inc.