Optimal Augmentation of a 2-Vertex-Connected Multigraph to a k-Edge-Connected and 3-Vertex-Connected Multigraph

Toshimasa Ishii (), Hiroshi Nagamochi () and Toshihide Ibaraki ()

Journal of Combinatorial Optimization, 2000, vol. 4, issue 1, No 3, 35-77

Abstract: 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 (search for similar items in EconPapers)
Date: 2000
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1023/A:1009884922499 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:4:y:2000:i:1:d:10.1023_a:1009884922499

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1023/A:1009884922499

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().