Augmenting a (k - 1)-Vertex-Connected Multigraph ℓ-Edge-Connected and k-Vertex-Connected Multigraph

被引：0

作者：

Toshimasa Ishii

Hiroshi Nagamochi

Toshihide Ibaraki

机构：

[1] Department of Information and Computer Sciences,

[2] Toyohashi University of Technology,undefined

[3] Toyohashi 441-8580,undefined

[4] Department of Applied Mathematics and Physics,undefined

[5] Graduate School of Informatics,undefined

[6] Kyoto University,undefined

[7] Kyoto 606-8501,undefined

[8] Department of Informatics,undefined

[9] School of Science and Technology,undefined

[10] Kwansei Gakuin University,undefined

[11] Sanda 669-1337,undefined

来源：

Algorithmica | 2006年 / 44卷

关键词：

Undirected multigraph; Edge-connectivity; Vertex-connectivity; Graph augmentation; Polynomial time approximation algorithm; Deterministic algorithm;

D O I：

暂无

中图分类号：

学科分类号：

摘要：

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

引用

页码：257 / 280

页数：23