基于不相交路徑技術(shù)的可靠網(wǎng)絡(luò)設(shè)計(jì).pdf

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

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

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