An Eight-Approximation Algorithm for Computing Rooted Three-Vertex Connected Minimum Steiner Networks

Hong Shen

doi:10.1109/TC.2012.170

Return

An Eight-Approximation Algorithm for Computing Rooted Three-Vertex Connected Minimum Steiner Networks

2013-09-01

PRE

Hong Shen *

郭

郭龙坤 (Longkun Guo)

DOI：10.1109/TC.2012.170

Original

Original request for help

Save

Abstract

En 中文

For a given undirected (edge) weighted graph G = (V, E), a terminal set S subset of V and a root r is an element of S, the rooted k-vertex connected minimum Steiner network (kVSMN(r)) problem requires to construct a minimum-cost subgraph of G such that each terminal in S \ {r} is k-vertex connected to r. As an important problem in survivable network design, the kVSMNr problem is known to be NP-hard even when k = 1 [14]. For k = 3 this paper presents a simple combinatorial eight-approximation algorithm, improving the known best ratio 14 of Nutov [20]. Our algorithm constructs an approximate 3VSMNr through augmenting a two-vertex connected counterpart with additional edges of bounded cost to the optimal. We prove that the total cost of the added edges is at most six times of the optimal by showing that the edges in a 3VSMNr compose a subgraph containing our solution in such a way that each edge appears in the subgraph at most six times.

Keywords:

Rooted three-vertex connectivity

survivable network design

Steiner minimum network

approximation algorithm

AI Summary

Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.