Department of Applied Mathematics & Physics, Kyoto Univiversity

Technical Report #98017 (December, 1998)

Optimal Augmentation of a 2-Vertex-Connected Multigraph to a $k$-Edge-Connected and 3-Vertex-Connected Multigraph
by Toshimasa Ishii, Hiroshi Nagamochi and Toshihide Ibaraki

Given an undirected multigraph $G=(V,E)$ and two positive integers $k$ and $\ell$, we consider the problem of augmenting $G$ by the smallest number of new edges to obtain a $k$-edge-connected and $\ell$-vertex-connected multigraph. In this paper, we show that the problem can be solved in $\tilde{O}(mn^2)$ time for any fixed $k$ and $\ell=3$ if an input multigraph $G$ is $2$-vertex-connected, where $n=|V|$ and $m$ is the number of pairs of adjacent vertices in $G$.