Efficient 2-Approximation Algorithms for Computing 2-Connected Steiner Minimal Networks

Hong Shen

doi:10.1109/TC.2011.123

Return

Efficient 2-Approximation Algorithms for Computing 2-Connected Steiner Minimal Networks

2012-07-01

PRE

Hong Shen *

郭

郭龙坤 (Longkun Guo)

DOI：10.1109/TC.2011.123

Original

Original request for help

Save

Abstract

En 中文

For an undirected and weighted graph G = (V, E) and a terminal set S subset of V, 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 [7], 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|(2)|S|(3)) time for computing a 2-vertex connected Steiner network (2V SN) whose weight is bounded by two times of the optimal solution 2-vertex connected SMN (2V SMN). It compares favorably with the currently known 2-approximation solution to the 2V SMN problem based on that to the survivable network design problem [10], [16], with a time complexity reduction of O(|V|(5)|E|(7)) for strongly polynomial time and O(|V|(5)gamma) for weakly polynomial time where gamma is determined by the sizes of input. Our algorithm applies a novel greedy approach to generate a 2V SN 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|(2)|S|(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.

Keywords:

Survivable network design

2-vertex (edge) connected Steiner minimal network

terminal spanning-tree

approximation algorithm

shortest disjoint path pair

Euler walk