Augmenting a (k -1)-Vertex-Connected Multigraph to an e-Edge-Connected and k-Vertex-Connected Multigraph

摘要

For two integers k, e ＞ 0 and an undirected multigraph G = (V, E), we consider the problem of augmenting G by the smallest number of new edges to obtain an e -edge-connected and k-vertex-connected multigraph. In this paper we show that a (k - 1)-vertex-connected multigraph G can be made £-edge-connected and k-vertex-connected by adding at most max{e + 1, 2k - 4} surplus edges over the optimum in 0(min[k, √n]kn~3 + n~4) time, where n = | V|.