A Unifying Augmentation Algorithm for Two-Edge Connectivity and Biconnectivity

Tsan Sheng Hsu; Ming Yang Kao

doi:10.1023/A:1009746026508

A Unifying Augmentation Algorithm for Two-Edge Connectivity and Biconnectivity

Tsan Sheng Hsu^*, Ming Yang Kao

^*Corresponding author for this work

Computer Science

Research output: Contribution to journal › Article › peer-review

8 Scopus citations

Abstract

Given an undirected graph G and two vertex subsets H₁ and H₂, 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 H₁ and two edge-disjoint paths between every pair of vertices in H₂. We present an algorithm to solve this problem in linear time. By properly setting H₁ and H₂, this augmentation algorithm subsumes existing optimal algorithms for several graph augmentation problems.

Original language	English (US)
Pages (from-to)	237-256
Number of pages	20
Journal	Journal of Combinatorial Optimization
Volume	2
Issue number	3
DOIs	https://doi.org/10.1023/A:1009746026508
State	Published - 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

Access to Document

10.1023/A:1009746026508

Cite this

@article{2510a8b85e0e4f92b27f9cb381a8278b,

title = "A Unifying Augmentation Algorithm for Two-Edge Connectivity and Biconnectivity",

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, Biconnectivity, Linear time algorithm, Two-edge connectivity",

author = "Hsu, {Tsan Sheng} and Kao, {Ming Yang}",

note = "Funding Information: Tsan-sheng Hsu{\textquoteright}s research supported in part by NSC Grants 85-2213-E-001-003 and 86-2213-E-001-012. Ming-Yang Kao{\textquoteright}s research supported in part by NSF Grant CCR-9531028. Copyright: Copyright 2018 Elsevier B.V., All rights reserved.",

year = "1998",

doi = "10.1023/A:1009746026508",

language = "English (US)",

volume = "2",

pages = "237--256",

journal = "Journal of Combinatorial Optimization",

issn = "1382-6905",

publisher = "Springer Netherlands",

number = "3",

}

TY - JOUR

T1 - A Unifying Augmentation Algorithm for Two-Edge Connectivity and Biconnectivity

AU - Hsu, Tsan Sheng

AU - Kao, Ming Yang

N1 - Funding Information: Tsan-sheng Hsu’s research supported in part by NSC Grants 85-2213-E-001-003 and 86-2213-E-001-012. Ming-Yang Kao’s research supported in part by NSF Grant CCR-9531028. Copyright: Copyright 2018 Elsevier B.V., All rights reserved.

PY - 1998

Y1 - 1998

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

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

KW - Bi-level augmentation

KW - Biconnectivity

KW - Linear time algorithm

KW - Two-edge connectivity

UR - http://www.scopus.com/inward/record.url?scp=0011523628&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0011523628&partnerID=8YFLogxK

U2 - 10.1023/A:1009746026508

DO - 10.1023/A:1009746026508

M3 - Article

AN - SCOPUS:0011523628

SN - 1382-6905

VL - 2

SP - 237

EP - 256

JO - Journal of Combinatorial Optimization

JF - Journal of Combinatorial Optimization

IS - 3

ER -

A Unifying Augmentation Algorithm for Two-Edge Connectivity and Biconnectivity

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this