E-E' with the minimum total weight, such that G0+E"=(V,E' E") has at least two internally disjoint paths between any pair of vertices in S. In this paper, we propose an O(|V||E|+ |V|2 log |V|) time algorithm 2-ABIS, whose performance ratio is 2 (3, respectively), for 2VCA-SV if G0 has a connected component containing S (otherwise)." />


A 2-Approximation Algorithm 2-ABIS for 2-Vertex-Connectivity Augmentation of Specified Vertices in a Graph

Makoto TAMURA  Satoshi TAOKA  Toshimasa WATANABE  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E86-A   No.4   pp.822-828
Publication Date: 2003/04/01
Online ISSN: 
DOI: 
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section of Selected Papers from the 15th Workshop on Circuits and Systems in Karuizawa)
Category: 
Keyword: 
graphs,  augmentation problems,  vertex-connectivity,  performance ratios,  polynomial time algorithms,  

Full Text: PDF(376.5KB)>>
Buy this Article




Summary: 
The 2-vertex-connectivity augmentation problem for specified vertices (2VCA-SV) is defined as follows: Given an undirected graph G=(V,E), a subgraph G0=(V,E') of G, a specified set of vertices S V and a weight function w:E R^+ (nonnegative real numbers), find a set E" E-E' with the minimum total weight, such that G0+E"=(V,E' E") has at least two internally disjoint paths between any pair of vertices in S. In this paper, we propose an O(|V||E|+ |V|2 log |V|) time algorithm 2-ABIS, whose performance ratio is 2 (3, respectively), for 2VCA-SV if G0 has a connected component containing S (otherwise).