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
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$.