基于不相交路徑技術的可靠網(wǎng)絡設計.pdf

1、隨著因特網(wǎng)中應用的爆炸性增長與網(wǎng)絡通訊技術的發(fā)展，無論在國防、財政和電源產(chǎn)業(yè)等傳統(tǒng)領域，還是在新興的可信計算和網(wǎng)絡、云計算系統(tǒng)和下一代互聯(lián)網(wǎng)等領域，網(wǎng)絡的可靠性都得到越來越多的重視。如何在最小化占用網(wǎng)絡資源的同時，通過網(wǎng)絡的拓撲結構提高網(wǎng)絡的可靠性，吸引了廣大研究者的興趣。在本文中，我們集中研究了這個課題中的兩個基礎問題：Min-Min 問題與Steiner 網(wǎng)絡問題。
　　 對于給定的帶權圖G=(V,E)以及源與目的結點s，t

2、,Min-Min 問題要求計算兩條不相交的-路徑，使得其中較短的路徑的權值最小。我們首先用一個反例指出了Bhatia等人關于無向圖中邊不相交Min-Min 問題的NP-完全性證明是不成立的；然后給出了該問題NP-完全性的一個正確證明。我們的證明基于一個從MAX-2SAT 問題的歸約。在此之后，我們研究了平面圖中的Min-Min 問題，并證明了Min-Min 問題在有向平面圖中是NP-完全的。我們這些關于Min-Min問題的工作填補了目前

3、理論上的一些空白。
　　 對于給定的帶權圖G=(V,E)、終端集S(∈)V以及給定的正整數(shù)，k-點/邊連通的Steiner 網(wǎng)絡問題要求計算的一個子圖，使得權值最小且終端間的點/邊連通度不小于。我們首先總結了已有文獻中Steiner網(wǎng)絡問題的相關工作，然后分別設計了2,3-點連通的Steiner網(wǎng)絡問題的近似比為2 與8的近似算法。
　　 接著，我們擴展了我們的算法，從得到了一個增加k-1邊連通的Steiner 網(wǎng)絡連通