TY - GEN

T1 - Approximate algorithms for survivable network design

AU - Shen, Hong

PY - 2012

Y1 - 2012

N2 - Along with the rapid development of network communication technology and the explosive growth of the internet applications, network reliability appears increasingly important to both traditional areas such as defense, finance and power industry, and emerging areas such as trusted computing, cloud computing and next-generation Internet. An interesting subject that has attracted great effort is how to design network topologies with a minimum network resource usage in terms of cost that provides a relibility guarantee. As problems on this subject, like most other network optimization problems, are well-known NP-hard even in their simplest form, design of effective solutions with a guaranteed approximation ratio from the optimal solution has been a major research focus of great significance for both theory and applications. This survery summarizes major existing techniques and results for solving some central problems in designing survivable networks including the minimal connected subgraph problem, the survivable network design problem and the Steiner minimal network problem.

AB - Along with the rapid development of network communication technology and the explosive growth of the internet applications, network reliability appears increasingly important to both traditional areas such as defense, finance and power industry, and emerging areas such as trusted computing, cloud computing and next-generation Internet. An interesting subject that has attracted great effort is how to design network topologies with a minimum network resource usage in terms of cost that provides a relibility guarantee. As problems on this subject, like most other network optimization problems, are well-known NP-hard even in their simplest form, design of effective solutions with a guaranteed approximation ratio from the optimal solution has been a major research focus of great significance for both theory and applications. This survery summarizes major existing techniques and results for solving some central problems in designing survivable networks including the minimal connected subgraph problem, the survivable network design problem and the Steiner minimal network problem.

KW - Approximation algorithm

KW - Connected spanning subgraph

KW - Disjoint path pair

KW - Euler walk

KW - Steiner minimal network

KW - Survivable network design

KW - Terminal spanning-tree

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

U2 - 10.1109/ICNC.2012.11

DO - 10.1109/ICNC.2012.11

M3 - Conference contribution

AN - SCOPUS:84874243290

SN - 9780769548937

T3 - Proceedings of the 2012 3rd International Conference on Networking and Computing, ICNC 2012

SP - 9

EP - 18

BT - Proceedings of the 2012 3rd International Conference on Networking and Computing, ICNC 2012

T2 - 2012 3rd International Conference on Networking and Computing, ICNC 2012

Y2 - 5 December 2012 through 7 December 2012

ER -