寻找最大带宽的独立路径对算法
DOI:
作者:
作者单位:

作者简介:

通讯作者:

中图分类号:

基金项目:

国家部委资助项目


Finding the widest pair of arc disjiont paths
Author:
Affiliation:

Fund Project:

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
  • |
  • 文章评论
    摘要:

    独立多路径算法在多径算法研究中具有重要地位。最小时延多路径问题的研究已较为成熟,而最大带宽多路径问题的研究却刚刚起步。文章介绍了有向图中链路独立路径对问题,提供了一种复杂度为O(mnlogn)求解该问题的多项式算法。该算法不需要考虑最大带宽链路独立路径对上流值分配问题,能够更好地应用到现实网络中。

    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.

    参考文献
    相似文献
    引证文献
引用本文

谢政,张晓明,陈挚.寻找最大带宽的独立路径对算法[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.

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2012-03-02
  • 最后修改日期:
  • 录用日期:
  • 在线发布日期: 2012-11-05
  • 出版日期:
文章二维码