• Complex
  • Title
  • Keyword
  • Abstract
  • Scholars
  • Journal
  • ISSN
  • Conference
成果搜索

author:

Shen, Hong (Shen, Hong.) [1] | Guo, Longkun (Guo, Longkun.) [2] (Scholars:郭龙坤)

Indexed by:

EI Scopus SCIE

Abstract:

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.

Keyword:

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

Community:

  • [ 1 ] [Shen, Hong]Beijing Jiaotong Univ, Sch Comp & Informat Technol, Beijing, Peoples R China
  • [ 2 ] [Shen, Hong]Univ Adelaide, Sch Comp Sci, Adelaide, SA 5005, Australia
  • [ 3 ] [Guo, Longkun]Fuzhou Univ, Sch Math & Comp Sci, Fuzhou 350108, Fujian, Peoples R China

Reprint 's Address:

  • [Shen, Hong]Beijing Jiaotong Univ, Sch Comp & Informat Technol, Beijing, Peoples R China

Show more details

Related Keywords:

Related Article:

Source :

IEEE TRANSACTIONS ON COMPUTERS

ISSN: 0018-9340

Year: 2012

Issue: 7

Volume: 61

Page: 954-968

1 . 3 7 9

JCR@2012

3 . 6 0 0

JCR@2023

ESI Discipline: COMPUTER SCIENCE;

JCR Journal Grade:2

CAS Journal Grade:3

Cited Count:

WoS CC Cited Count: 4

SCOPUS Cited Count: 5

ESI Highly Cited Papers on the List: 0 Unfold All

WanFang Cited Count:

Chinese Cited Count:

30 Days PV: 0

Online/Total:236/10043657
Address:FZU Library(No.2 Xuyuan Road, Fuzhou, Fujian, PRC Post Code:350116) Contact Us:0591-22865326
Copyright:FZU Library Technical Support:Beijing Aegean Software Co., Ltd. 闽ICP备05005463号-1