论文部分内容阅读
在本文中，我们研究了计算机网络通讯中一类重要问题，不相交路径问题．问题为：给出图G=(V,E)以及图中的两点s，t，我们要求从点s到点t的两条不相交路径(点不相交或者边不相交)，并且满足某个目标函数．我们研究了在不同的目标函数下，这些问题的复杂性，这些目标包括：MinMax，MinMin，Balanced，MinSum-MinMax，MinSum-MinMin，Multi-objective，ConstrainedMulti-objective．
对MinMax2DP问题，我们给出了，在DAG上的解决该问题的FPTAS算法．
对MinMin2DP问题，我们证明了，四种版本的问题都是强NP完全的．
对Balanced2DP问题，我们证明其四种版本都是强NP完全的，并且都不存在常数近似度的近似算法．而对于DAG的情况，我们证明其为NP完全的，并且给出了伪多项式时间的算法．
对MinSum-MinMax2DP问题，我们证明，对于无向图，该问题是NP完全的，并且存在近似度为2的近似算法．对有向图，该问题是强NP完全的，存在近似度为2的近似算法，并且不存在近似度小于2的近似算法，除非P=NP．对于DAG，该问题是NP完全的，并且存在FPTAS．
对MinSum-MinMin2DP问题，在DAG的情况下，我们给出了一个快速的多项式时间算法．
对多目标优化2DP问题，我们证明对于DAG的情况，存在FPTAS算法．而对于带约束多目标优化2DP问题，在DAG的情况下，存在多项式时间的(1+α，1+β)近似算法．同时我们还从一些角度分析，提出对一般情况这两个问题可能不存在FPTAS算法．