A Unifying Augmentation Algorithm for Two-Edge Connectivity and Biconnectivity |
| |
Authors: | Tsan-sheng Hsu Ming-Yang Kao |
| |
Affiliation: | (1) Institute of Information Science, Academia Sinica, Nankang, 11529, Taipei Taiwan, ROC;(2) Department of Computer Science, Yale University, New Haven, CT 06520, USA |
| |
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 |
本文献已被 SpringerLink 等数据库收录! |
|