TY - JOUR

T1 - Efficient 2-approximation algorithms for computing 2-connected steiner minimal networks

AU - Shen, Hong

AU - Guo, Longkun

N1 - Funding Information:
This work was supported by National Science Foundation of China under its General Projects funding #61170232, Fundamental Research Funds for the Central Universities #2012JBZ017, State Key Laboratory of Rail Traffic Control and Safety Research Grant #RCS2011ZT009, and Research Initiative Grant of Beijing Jiaotong University #2010RC018, and was partially done during the authors stay at the University of Science and Technology of China.

PY - 2012

Y1 - 2012

N2 - For an undirected and weighted graph G=(V,E) and a terminal set SV, the 2-connected Steiner minimal network (SMN) problem requires to compute a minimum-weight subgraph of G in which all terminals are 2-connected to each other. This problem has important applications in design of survivable networks and fault-tolerant communication, and is known MAXSNP-hard , a harder subclass of NP-hard problems for which no polynomial-time approximation scheme (PTAS) is known. This paper presents an efficient algorithm of O(V 2S 3) time for computing a 2-vertex connected Steiner network (2VSN) whose weight is bounded by two times of the optimal solution 2-vertex connected SMN (2VSMN). It compares favorably with the currently known 2-approximation solution to the 2VSMN problem based on that to the survivable network design problem], with a time complexity reduction of O(V 5E 7) for strongly polynomial time and O(V 5γ ) for weakly polynomial time where γ is determined by the sizes of input. Our algorithm applies a novel greedy approach to generate a 2VSN through progressive improvement on a set of vertex-disjoint shortest path pairs incident with each terminal of S. The algorithm can be directly deployed to solve the 2-edge connected SMN problem at the same approximation ratio within time O(V 2S 2). To the best of our knowledge, this result presents currently the most efficient 2-approximation algorithm for the 2-connected Steiner minimal network problem.

AB - For an undirected and weighted graph G=(V,E) and a terminal set SV, the 2-connected Steiner minimal network (SMN) problem requires to compute a minimum-weight subgraph of G in which all terminals are 2-connected to each other. This problem has important applications in design of survivable networks and fault-tolerant communication, and is known MAXSNP-hard , a harder subclass of NP-hard problems for which no polynomial-time approximation scheme (PTAS) is known. This paper presents an efficient algorithm of O(V 2S 3) time for computing a 2-vertex connected Steiner network (2VSN) whose weight is bounded by two times of the optimal solution 2-vertex connected SMN (2VSMN). It compares favorably with the currently known 2-approximation solution to the 2VSMN problem based on that to the survivable network design problem], with a time complexity reduction of O(V 5E 7) for strongly polynomial time and O(V 5γ ) for weakly polynomial time where γ is determined by the sizes of input. Our algorithm applies a novel greedy approach to generate a 2VSN through progressive improvement on a set of vertex-disjoint shortest path pairs incident with each terminal of S. The algorithm can be directly deployed to solve the 2-edge connected SMN problem at the same approximation ratio within time O(V 2S 2). To the best of our knowledge, this result presents currently the most efficient 2-approximation algorithm for the 2-connected Steiner minimal network problem.

KW - 2-vertex (edge) connected Steiner minimal network

KW - Euler walk

KW - Survivable network design

KW - approximation algorithm

KW - shortest disjoint path pair

KW - terminal spanning-tree

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

U2 - 10.1109/TC.2011.123

DO - 10.1109/TC.2011.123

M3 - Article

AN - SCOPUS:84861822653

SN - 0018-9340

VL - 61

SP - 954

EP - 968

JO - IEEE Transactions on Computers

JF - IEEE Transactions on Computers

IS - 7

M1 - 5953583

ER -