Augmenting a (k - 1)-Vertex-Connected Multigraph ℓ-Edge-Connected and k-Vertex-Connected Multigraph

For two integers $k,\ell > 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 $\ell$-edge-connected and $k$-vertex-connected multigraph. In this paper we show that a $(k-1)$-vertex-connected multigraph $G$ can be made $\ell$-edge-connected and $k$-vertex-connected by adding at most $\bound$ surplus edges over the optimum in $O(\tm)$ time, where $n=|V|$.