| 引用本文: | 谢政,张晓明,陈挚.寻找最大带宽的独立路径对算法.[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[点击复制] |
|
| |
|
|
| 本文已被：浏览 7122次 下载 6237次 |
| 寻找最大带宽的独立路径对算法 |
| 谢政, 张晓明, 陈挚 |
|
(国防科技大学 理学院,湖南 长沙 410073)
|
| 摘要: |
| 独立多路径算法在多径算法研究中具有重要地位。最小时延多路径问题的研究已较为成熟，而最大带宽多路径问题的研究却刚刚起步。文章介绍了有向图中链路独立路径对问题，提供了一种复杂度为O(mnlogn)求解该问题的多项式算法。该算法不需要考虑最大带宽链路独立路径对上流值分配问题，能够更好地应用到现实网络中。 |
| 关键词: 多路径 链路独立 最大带宽路径对 容量 WPAP |
| DOI： |
| 投稿日期：2012-03-02 |
| 基金项目:国家部委资助项目 |
|
| Finding the widest pair of arc disjiont paths |
| XIE Zheng, ZHANG Xiaoming, CHEN Zhi |
|
(College of Science, National University of Defense Technology, Changsha 410073, China)
|
| Abstract: |
| 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. |
| Keywords: multipath arc-disjoint widest pair capacity WPAP（Widest Pair of Arc-disjoint Paths) |
|
|
|
|
|
