独立多路径算法在多径算法研究中具有重要地位.最小时延多路径问题的研究已较为成熟,而最大带宽多路径问题的研究却刚刚起步.文章介绍了有向图中链路独立路径对问题,提供了一种复杂度为O(mnlogn)求解该问题的多项式算法.该算法不需要考虑最大带宽链路独立路径对上流值分配问题,能够更好地应用到现实网络中.%Disjoint paths routing catches special attention in multipath research. Shortest disjoint paths problem has been studied maturely, while the research of widest disjoint paths problem is just under development. In this paper, we presented a problem of finding the widest pair of arc-disjoint paths in a directed graph. It differs from Multipath Flows, which may be transformed into the problem of Maximum Flow and Minimum Cut. Then we propose a polynomial algorithm for it with time complexity O( mnlogn). It is not required to reassign flux at common vertices on the widest pair of paths, and this scheme can be implemented easier in real networks.
展开▼
