Augmenting a(k—1)-Vertex-ConnectedMultigraph to an ℓ-Edge-Connected and k-Vertex-Connected Multigraph

Given an undirected multigraph G = (V,E) and two positive integers l and k, 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 an (k - 1)-vertex-connected multigraph G (k ? 4) can be made l-edge-connected and k-vertex-connected by adding at most 2l surplus edges over the optimum, in O(min{k,?n}kn3 + n4) time, where n = |V|.