A Unifying Augmentation Algorithm for Two-Edge Connectivity and Biconnectivity

Tsan-sheng Hsu () and Ming-Yang Kao ()
Additional contact information
Tsan-sheng Hsu: Institute of Information Science, Academia Sinica, Nankang
Ming-Yang Kao: Yale University

Journal of Combinatorial Optimization, 1998, vol. 2, issue 3, No 3, 237-256

Abstract: Abstract Given an undirected graph G and two vertex subsets H1 and H2, the bi-level augmentation problem is that of adding to G the smallest number of edges such that the resulting graph contains two internally vertex-disjoint paths between every pair of vertices in H1 and two edge-disjoint paths between every pair of vertices in H2. We present an algorithm to solve this problem in linear time. By properly setting H1 and H2, this augmentation algorithm subsumes existing optimal algorithms for several graph augmentation problems.

Keywords: bi-level augmentation; two-edge connectivity; biconnectivity; linear time algorithm (search for similar items in EconPapers)
Date: 1998
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1023/A:1009746026508 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:2:y:1998:i:3:d:10.1023_a:1009746026508

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

DOI: 10.1023/A:1009746026508

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 ().