關于兩不相交路徑問題的研究.pdf

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

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

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