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

摘要

The 2-vertex-conner,tivity augmentation problem for specified vertices (2VCA-SV) is defined as follows: Given an undirected graph G = (V, E), a subgraph G_0 = (V, E′) of G, a specified set of vertices S is contained in V and a weight function w : E → R~+ (nonnegative real numbers), find a set E″is contained in E — E′ with the minimum total weight, such that G_0 + 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 G_0 has a connected component containing S (otherwise).