A NOTE ON THE VERTEX-CONNECTIVITY AUGMENTATION PROBLEM

Using the polynomial algorithm given in [T. Jordan, On the optimal ver tex-connectivity augmentation, J. Combin. Theory Ser. B 63 (1995), 8-2 0] a k-connected undirected graph G=(V, E) san be made (k + 1)-connect ed by adding at most k - 2. surplus edges over (a lower bound of) the optimum. Here we introduce two new lower bounds and show that in fact the size of the solution given by (a slightly modified version of) thi s algorithm differs from the optimum by at most [(k-1)/2]. (C) 1997 Ac ademic Press.