Department of Applied Mathematics & Physics, Kyoto University

Technical Report 2000-006 (September 12, 2000)

Minimum Augmentation of a Multigraph to an $\ell$-Edge and 3-Vertex Connectivity Multigraph
by Toshimasa Ishii, Hiroshi Nagamochi and Toshihide Ibaraki

PostScript File

Given an undirected multigraph $G=(V,E)$ and two positive integers $\ell$ and $k$, the edge-and-vertex connectivity augmentation problem asks to augment $G$ by the smallest number of new edges so that the resulting multigraph becomes $\ell$-edge-connected and $k$-vertex-connected. In this paper, we show that the problem can be solved in polynomial time for any fixed $\ell$ and $k=3$.