E-E' with the minimum total weight, such that G0+E"=(V,E'
For Full-Text PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
A 2-Approximation Algorithm 2-ABIS for 2-Vertex-Connectivity Augmentation of Specified Vertices in a Graph
Makoto TAMURA Satoshi TAOKA Toshimasa WATANABE
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences Vol.E86-A No.4 pp.822-828
Publication Date: 2003/04/01
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)
graphs, augmentation problems, vertex-connectivity, performance ratios, polynomial time algorithms,
Full Text: PDF(376.5KB)>>
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).