Journal of Computer Applications ›› 2015, Vol. 35 ›› Issue (5): 1246-1249.DOI: 10.11772/j.issn.1001-9081.2015.05.1246

Previous Articles     Next Articles

New algorithm for problem of minimum cut/maximum flow based on augmenting path restoration

ZHAO Lifeng, YAN Ziheng   

  1. School of Science, Nanjing University of Posts and Telecommunications, Nanjing Jiangsu 210000, China
  • Received:2014-12-10 Revised:2015-01-23 Online:2015-05-10 Published:2015-05-14

基于增广链修复的最大流求解算法

赵礼峰, 严子恒   

  1. 南京邮电大学 理学院, 南京 210000
  • 通讯作者: 严子恒
  • 作者简介:赵礼峰(1959-),男,安徽淮北人,教授,主要研究方向:图论及其应用、矩阵论; 严子恒(1991-),男,江苏南京人,硕士研究生,主要研究方向:网络最大流、最小费用流.

Abstract:

The NW (Newman-Watts) small-world network and the BA (Barabasi-Albert) scale-free network are two kinds of common network in reality, these two kinds of networks have a highly possibility existing multiple paths between any pair of vertexes. If abandoning saturated augmented chain and finding augmented chain, the efficiency is not high. The fact above urged a high performance new algorithm described as minimum cut/maximum flow algorithm based on augmenting path restoration to manage these two networks. The new algorithm constantly sought vertexes following greedy heuristics to restore saturated augmenting paths which generated by adjusting flow on shortest paths. By experimental comparisons on the NW small-world network and the BA scale-free network, the new algorithm was several times faster than Ford-Fulkerson algorithm and half as Dinic algorithm in RAM usage, as a consequence, the new algorithm was capable of calculating growing telecommunication and traffic networks.

Key words: maximum flow, augmenting path, augmenting path restoration, NW small-world network, BA scale-free network

摘要:

NW小世界网络及BA无标度网络是现实中常见的两种网络,这两种网络中任意两点之间有极大可能存在多条路径,若舍弃饱和增广链并重新寻找增广链,则效率不高,因此针对网络的这一特性提出了一种增广链修复的最大流求解算法.该算法沿最短增广链调整流量后,保留路径上残余的非饱和弧,并用贪心法则选择合适的中继节点修复断开的增广链,提高增广链使用效率.通过对NW小世界网络和BA无标度网络建模仿真,得到并验证了所提算法在这两种网络上的运行速度数倍于Ford-Fulkerson算法且其空间复杂度仅有Dinic算法的一半,因此所提算法能够高效处理更大规模网络流问题,以适应日益膨胀的通信网络和交通运输网络.

关键词: 最大流, 增广链, 增广链修复, NW小世界网络, BA无标度网络

CLC Number: