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

Hong Shen, Longkun Guo

Research output: Contribution to journalArticlepeer-review

5 Citations (Scopus)


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.

Original languageEnglish
Article number5953583
Pages (from-to)954-968
Number of pages15
JournalIEEE Transactions on Computers
Issue number7
Publication statusPublished - 2012
Externally publishedYes


  • 2-vertex (edge) connected Steiner minimal network
  • Euler walk
  • Survivable network design
  • approximation algorithm
  • shortest disjoint path pair
  • terminal spanning-tree


Dive into the research topics of 'Efficient 2-approximation algorithms for computing 2-connected steiner minimal networks'. Together they form a unique fingerprint.

Cite this