TY - JOUR

T1 - An eight-approximation algorithm for computing rooted three-vertex connected minimum steiner networks

AU - Shen, Hong

AU - Guo, Longkun

PY - 2013

Y1 - 2013

N2 - For a given undirected (edge) weighted graph (G=(V,E)), a terminal set (S ⊂ V) and a root (r ∈ S), the rooted (k)-vertex connected minimum Steiner network (kVSMNr) 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 (kVSMN r) problem is known to be NP-hard even when (k=1). For (k=3) this paper presents a simple combinatorial eight-approximation algorithm, improving the known best ratio 14 of Nutov. 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.

AB - For a given undirected (edge) weighted graph (G=(V,E)), a terminal set (S ⊂ V) and a root (r ∈ S), the rooted (k)-vertex connected minimum Steiner network (kVSMNr) 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 (kVSMN r) problem is known to be NP-hard even when (k=1). For (k=3) this paper presents a simple combinatorial eight-approximation algorithm, improving the known best ratio 14 of Nutov. 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.

KW - Approximation algorithm

KW - Rooted three-vertex connectivity

KW - Steiner minimum network

KW - Survivable network design

UR - http://www.scopus.com/inward/record.url?scp=84881134365&partnerID=8YFLogxK

U2 - 10.1109/TC.2012.170

DO - 10.1109/TC.2012.170

M3 - Article

AN - SCOPUS:84881134365

SN - 0018-9340

VL - 62

SP - 1684

EP - 1693

JO - IEEE Transactions on Computers

JF - IEEE Transactions on Computers

IS - 9

M1 - 6235951

ER -