Approximate algorithms for survivable network design

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

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 subgraph problem, the survivable network design problem and the Steiner minimal network problem.

Original languageEnglish
Title of host publicationProceedings of the 2012 3rd International Conference on Networking and Computing, ICNC 2012
Pages9-18
Number of pages10
DOIs
Publication statusPublished - 2012
Externally publishedYes
Event2012 3rd International Conference on Networking and Computing, ICNC 2012 - Naha, Okinawa, Japan
Duration: 5 Dec 20127 Dec 2012

Publication series

NameProceedings of the 2012 3rd International Conference on Networking and Computing, ICNC 2012

Conference

Conference2012 3rd International Conference on Networking and Computing, ICNC 2012
Country/TerritoryJapan
CityNaha, Okinawa
Period5/12/127/12/12

Keywords

  • Approximation algorithm
  • Connected spanning subgraph
  • Disjoint path pair
  • Euler walk
  • Steiner minimal network
  • Survivable network design
  • Terminal spanning-tree

Fingerprint

Dive into the research topics of 'Approximate algorithms for survivable network design'. Together they form a unique fingerprint.

Cite this