Augmenting a (k-1)-vertex-connected multigraph to an l-edge-connected and k-vertex-connected multigraph
For two integers k, l > 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 l-edge-connected and k-vertex-connected multigraph. In this paper we show that a (k - 1)-vertex-connected multigraph G can be made l-edge-connected and k-vertex-connected by adding at most max{l + 1, 2k - 4} surplus edges over the optimum in O( min{k,root n}kn(3) + n(4)) time, where n = vertical bar V vertical bar.
undirected multigraph edge-connectivity vertex-connectivity graph augmentation polynomial time approximation algorithm deterministic algorithm