A (2 - 2/|L|)-Approximation Algorithm R2VS or R2ES to 2-Vertex- or 2-Edge-Connect Specified Vertices in a Graph

概要

論文の詳細を見る
The 2-vertex-connectivity (2-edge-connectivity, respectively) augmentation problem for specified vertices, 2VCA-SV (2ECA-SV) for short, is defined as follows: "Given an undirected graph G = (V, E), a spanning subgraph G' = (V, E') of G, specified 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 G' + E" = (V, E' ∪ E") has at least two internally disjoint (edge disjoint) paths between any pair of vertices in S. In this paper, we propose a (2 - 2/|L|)-approximation algorithm R2VC or R2EC for 2VCA-SV or 2ECA-SV, respectively, if G' has a connected component containing S. where L is the set of leaves of a certain tree constructed from G' and S. Its time or space complexity is O(|V||E| + |V|^2 log |V| + |L||V|^2) or O(|V|^2), respectively.
一般社団法人情報処理学会の論文
2002-11-08