DocumentCode :
3137467
Title :
Approximate Algorithms for Survivable Network Design
Author :
Hong Shen
Author_Institution :
Sch. of Comput. Sci., Univ. of Adelaide, Adelaide, SA, Australia
fYear :
2012
fDate :
5-7 Dec. 2012
Firstpage :
9
Lastpage :
18
Abstract :
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 sub graph problem, the survivable network design problem and the Steiner minimal network problem.
Keywords :
Internet; approximation theory; computational complexity; computer network reliability; graph theory; telecommunication network topology; Internet applications; NP-hard; Steiner minimal network problem; approximate algorithms; cloud computing; minimal connected subgraph; network communication technology; network reliability; network topologies; next-generation Internet; survivable network design; trusted computing; Approximation algorithms; Approximation methods; Cascading style sheets; High definition video; Optimization; Reliability; Transforms; Approximation algorithm; Euler walk; Steiner minimal network; connected spanning subgraph; disjoint path pair; survivable network design; terminal spanning-tree;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Networking and Computing (ICNC), 2012 Third International Conference on
Conference_Location :
Okinawa
Print_ISBN :
978-1-4673-4624-5
Type :
conf
DOI :
10.1109/ICNC.2012.11
Filename :
6424537
Link To Document :
بازگشت