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