Design Of Survivable Networks Based On Disjoint Paths

Along with the rapid development of network communication technology and the explosive growth of the internet applications, network reliability is attracting more and more attention, because of its applications in both traditional areas such as defense, finance and power industry, and emerging areas such as trusted computing, cloud computing and next-generation Internet. In this dissertation we focus on improving network reliability while minimizing network resource usage, and tackle two basic problems on this topic:the Min-Min problem and the Steiner network problem.For a given weighted graph G=(V, E), a source vertex s and a destination vertex t, the Min-Min problem requires to compute two disjoint st-paths, such that the weight of the shorter path is minimized. In this dissertation, we first show that Bhatia et al's NP-completeness proof on the edge-disjoint Min-Min problem in undirected graph is flawed by giving a counter example, and secondly give a correct NP-completeness proof for this problem based on a reduction from the MAX-2SAT problem. Then, we consider the Min-Min problem in planar graphs, and show that the edge-disjoint Min-Min problem is NP-complete in planar digraphs by giving a reduction from the 3SAT problem.For a given weighted graph G=(V,E), a terminal set S(?)V, and a positive integer k, the k-vertex/edge-connected minimum Steiner network problem requires to compute a subgraph H C G, such that H contains k vertex/edge disjoint paths between every pair of terminals in S while the weight of H is minimized. We survey the related work on the minimum Steiner network problem, and then present approximation algorithms for the 2,3-vertex connected Steiner network problem with approximate ratios 2 and 8 respectively. Then we extend our algorithm and obtain a 2-approximation algorithm for augmenting a (k-1)-edge connected Steiner network to a k-edge connected Steiner network. Finally, we show that our algorithm can not be extended to solve the k-vertex connected minimum Steiner network problem.