A Unifying Augmentation Algorithm for Two-Edge Connectivity and Biconnectivity

Tsan Sheng Hsu*, Ming Yang Kao

*Corresponding author for this work

Research output: Contribution to journalArticle

8 Scopus citations

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.

Original languageEnglish (US)
Pages (from-to)237-256
Number of pages20
JournalJournal of Combinatorial Optimization
Volume2
Issue number3
DOIs
StatePublished - Jan 1 1998

Keywords

  • Bi-level augmentation
  • Biconnectivity
  • Linear time algorithm
  • Two-edge connectivity

ASJC Scopus subject areas

  • Computer Science Applications
  • Discrete Mathematics and Combinatorics
  • Control and Optimization
  • Computational Theory and Mathematics
  • Applied Mathematics

Fingerprint Dive into the research topics of 'A Unifying Augmentation Algorithm for Two-Edge Connectivity and Biconnectivity'. Together they form a unique fingerprint.

  • Cite this