Optimal Augmentation of a 2-Vertex-Connected Multigraph to a k-Edge-Connected and 3-Vertex-Connected Multigraph |
| |
| Authors: | Toshimasa Ishii Hiroshi Nagamochi Toshihide Ibaraki |
| |
| Institution: | (1) Department of Information and Computer Sciences, Toyohashi University of Technology, Tempaku, Toyohashi, 441-8580, Japan;(2) 1st Laboratory, Development Laboratories, NEC Networks Abiko, Chiba, 270-1198, Japan;(3) Department of Applied Mathematics and Physics, Kyoto University, Sakyo, Kyoto, 606-8501, Japan |
| |
| Abstract: | Given an undirected multigraph G = (V, E) and two positive integers  and k, we consider the problem of augmenting G by the smallest number of new edges to obtain an -edge-connected and k-vertex-connected multigraph. In this paper, we show that the problem can be solved in Õ(mn2) time for any fixed and k = 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. |
| |
| Keywords: | undirected multigraph edge-connectivity vertex-connectivity graph augmentation polynomial deterministic algorithm |
| 本文献已被 SpringerLink 等数据库收录！ |
|
