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.
参考文献
相似文献
引证文献
引用本文
谢政,张晓明,陈挚.寻找最大带宽的独立路径对算法[J].国防科技大学学报,2012,34(5):158-163. XIE Zheng, ZHANG Xiaoming, CHEN Zhi. Finding the widest pair of arc disjiont paths[J]. Journal of National University of Defense Technology,2012,34(5):158-163.