關(guān)于兩不相交路徑問題的研究.pdf

1、在本文中，我們研究了計(jì)算機(jī)網(wǎng)絡(luò)通訊中一類重要問題，不相交路徑問題．問題為：給出圖G=(V,E)以及圖中的兩點(diǎn)s，t，我們要求從點(diǎn)s到點(diǎn)t的兩條不相交路徑(點(diǎn)不相交或者邊不相交)，并且滿足某個(gè)目標(biāo)函數(shù)．我們研究了在不同的目標(biāo)函數(shù)下，這些問題的復(fù)雜性，這些目標(biāo)包括：MinMax，MinMin，Balanced，MinSum-MinMax，MinSum-MinMin，Multi-objective，ConstrainedMulti-objec

2、tive． 對(duì)MinMax2DP問題，我們給出了，在DAG上的解決該問題的FPTAS算法． 對(duì)MinMin2DP問題，我們證明了，四種版本的問題都是強(qiáng)NP完全的． 對(duì)Balanced2DP問題，我們證明其四種版本都是強(qiáng)NP完全的，并且都不存在常數(shù)近似度的近似算法．而對(duì)于DAG的情況，我們證明其為NP完全的，并且給出了偽多項(xiàng)式時(shí)間的算法． 對(duì)MinSum-MinMax2DP問題，我們證明，對(duì)于無向圖，該問題

3、是NP完全的，并且存在近似度為2的近似算法．對(duì)有向圖，該問題是強(qiáng)NP完全的，存在近似度為2的近似算法，并且不存在近似度小于2的近似算法，除非P=NP．對(duì)于DAG，該問題是NP完全的，并且存在FPTAS． 對(duì)MinSum-MinMin2DP問題，在DAG的情況下，我們給出了一個(gè)快速的多項(xiàng)式時(shí)間算法． 對(duì)多目標(biāo)優(yōu)化2DP問題，我們證明對(duì)于DAG的情況，存在FPTAS算法．而對(duì)于帶約束多目標(biāo)優(yōu)化2DP問題，在DAG的情況下，存