Augmenting a (k - 1)-Vertex-Connected
Multigraph ℓ-Edge-Connected and k-Vertex-Connected Multigraph |
| |
| Authors: | Toshimasa Ishii Hiroshi Nagamochi Toshihide Ibaraki |
| |
| Affiliation: | (1) Department of Information and Computer Sciences, Toyohashi University of Technology, Toyohashi 441-8580, Japan;(2) Department of Applied Mathematics and Physics, Graduate School of Informatics, Kyoto University, Kyoto 606-8501, Japan;(3) Department of Informatics, School of Science and Technology,Kwansei Gakuin University, Sanda 669-1337, Japan |
| |
| Abstract: | 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|$. |
| |
| Keywords: | Undirected multigraph Edge-connectivity Vertex-connectivity Graph augmentation Polynomial time approximation algorithm Deterministic algorithm |
| 本文献已被 SpringerLink 等数据库收录！ |
|
