A 2-approximation algorithm <i>2-ABIS</i> for 2-vertex- connectivity augmentation of specified vertices in a graph

作     者：Tamura, M Taoka, S Watanabe, T 

作者机构：Hiroshima Univ Grad Sch Engn Higashihiroshima 7398527 Japan 

出 版 物：《IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES》 (电子信息通信学会汇刊：电子学、通信及计算机科学基础)

年 卷 期：2003年第E86A卷第4期

页      面：822-828页

核心收录：

学科分类：0808[工学-电气工程] 0809[工学-电子科学与技术（可授工学、理学学位）] 08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：graphs augmentation problems vertex-connectivity performance ratios polynomial time algorithms 

摘      要：The 2-vertex-connectivity 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 C V and a weight function w : E -- R+ (nonnegative real numbers), find a set E subset of or equal to E - E with the minimum total weight, such that G(0) + E (V, E boolean OR E) has at least two internally disjoint paths between any pair of vertices in S. In this paper, we propose an O(\Vparallel toE\ + \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).