Please use this identifier to cite or link to this item:
https://hdl.handle.net/2440/72384
Citations | ||
Scopus | Web of Science® | Altmetric |
---|---|---|
?
|
?
|
Type: | Journal article |
Title: | Efficient 2-approximation algorithms for computing 2-connected Steiner minimal networks |
Author: | Shen, H. Guo, L. |
Citation: | IEEE Transactions on Computers, 2012; 61(7):954-968 |
Publisher: | IEEE Computer Soc |
Issue Date: | 2012 |
ISSN: | 0018-9340 1557-9956 |
Statement of Responsibility: | Hong Shen and Longkun Guo |
Abstract: | For an undirected and weighted graph G = (V,E) and a terminal set S 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 OVj2jSj3Þ 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ðjV j5jEj7Þ for strongly polynomial time and OðjV j5_Þ for weakly polynomial time where _ 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ðjV j2jSj2Þ. 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 approximationalgorithm, shortest disjoint path pair, Euler walk. |
Rights: | © 2012 IEEE |
DOI: | 10.1109/TC.2011.123 |
Published version: | http://dx.doi.org/10.1109/tc.2011.123 |
Appears in Collections: | Aurora harvest 5 Computer Science publications |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
RA_hdl_72384.pdf Restricted Access | Restricted Access | 786.7 kB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.