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

doi:10.11772/j.issn.1001-9081.2015.05.1246

计算机应用 ›› 2015, Vol. 35 ›› Issue (5): 1246-1249.DOI: 10.11772/j.issn.1001-9081.2015.05.1246

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

赵礼峰, 严子恒

南京邮电大学理学院, 南京 210000

收稿日期:2014-12-10 修回日期:2015-01-23 发布日期:2015-05-14 出版日期:2015-05-10
通讯作者: 严子恒
作者简介:赵礼峰(1959-),男,安徽淮北人,教授,主要研究方向:图论及其应用、矩阵论; 严子恒(1991-),男,江苏南京人,硕士研究生,主要研究方向:网络最大流、最小费用流.

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

ZHAO Lifeng, YAN Ziheng

School of Science, Nanjing University of Posts and Telecommunications, Nanjing Jiangsu 210000, China

Received:2014-12-10 Revised:2015-01-23 Online:2015-05-14 Published:2015-05-10

摘要/Abstract

摘要：

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

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

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

中图分类号:

TP301.6

赵礼峰, 严子恒. 基于增广链修复的最大流求解算法[J]. 计算机应用, 2015, 35(5): 1246-1249.

ZHAO Lifeng, YAN Ziheng. New algorithm for problem of minimum cut/maximum flow based on augmenting path restoration[J]. Journal of Computer Applications, 2015, 35(5): 1246-1249.

参考文献

[1] XIE Z. Network algorithm and complexity theory[M]. Changsha: National Defense University Press, 2003: 144-147.(谢政. 网络算法与复杂性理论[M]. 长沙:国防科技大学出版社,2003: 144-147.)
[2] DINIC E A. Algorithms for solution of a problem of maximum flow in networks with power estimation[J]. Soviet Mathematics: Doklady, 1970, 11(8):1277-1280.
[3] EDMONDS J, KARP R M. Theoretical improvements in algorithmic efficiency for network flow problems[J]. Journal of the ACM, 1972, 19(2): 248-264.
[4] GOLDBERG A V, RAO S. Beyond the flow decomposition barrier[J]. Journal of the ACM, 1998, 45(5): 783-797.
[5] BOYKOV Y, KOLMOGOROV V. An experimental comparison of min-cut/max-flow algorithms for energy minimization in vision[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2004, 26(9):1124-1137.
[6] HE Z, HONG B. Dynamically tuned push-relabel algorithm for the maximum flow problem on CPU-GPU-hybrid platforms[C]// Proceedings of the 2010 IEEE International Symposium on Parallel and Distributed Processing. Piscataway: IEEE, 2010: 1-10.
[7] NEWMAN M E J, WATTS D J. Renormalization group analysis of the small-world network model[J]. Physics Letters A, 1999, 263(4): 341-346.
[8] TIAN L, WANG J, YAN C, et al. Hemisphere-and gender-related differences in small-world brain networks: a resting-state functional MRI study[J]. Neuroimage, 2011, 54(1): 191-202.
[9] JANCKE L, LANGER N. A strong parietal hub in the small-world network of coloured-hearing synaesthetes during resting state EEG[J]. Journal of Neuropsychology, 2011, 5(2): 178-202.
[10] BARABASI A L, ALBERT R. Emergence of scaling in random networks[J]. Science, 1999, 286(5439): 509-512.
[11] CASTELLANO C, PASTOR-SATORRAS R. Routes to thermodynamic limit on scale-free networks[J]. Physical Review Letters, 2008, 100(14): 148701.
[12] ERDOS P, RENYI A. On the evolution of random graphs[D]. Budapest: Mathematical Institute of the Hungarian Academy of Sciences, 1960: 17-61.
[13] FORGERINI F L, DOROGOVTSEV S N, MENDES J F F. Emergence of scale-free networks from optimization process[J].Journal of Physics: Conference Series, 2013, 410(1): 012094.
[14] GENIO C I, GROSS T, BASSLER K E. All scale-free networks are sparse[J]. Physical Review Letters, 2011, 107(17): 178701.

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

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

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 11

编辑推荐

Metrics

[1]	郑李萍, 王建强, 张玉召, 董祚帆. 多时空配送任务驱动的无人车队车辆数优化方法[J]. 计算机应用, 2021, 41(5): 1406-1411.
[2]	李梓杨, 于炯, 卞琛, 鲁亮, 蒲勇霖. 基于流网络的流式计算动态任务调度策略[J]. 计算机应用, 2018, 38(9): 2560-2567.
[3]	胡章芳, 秦阳鸿. 基于图割理论的尺度自适应人脸跟踪算法[J]. 计算机应用, 2017, 37(4): 1189-1192.
[4]	王仁群, 彭力. 数据中心网络拓扑感知型拥塞控制算法[J]. 计算机应用, 2016, 36(9): 2357-2361.
[5]	黄承真王雷刘小龙况亚萍. Hadoop任务分配策略的改进[J]. 计算机应用, 2013, 33(08): 2158-2162.
[6]	牛瑞芳刘勇. 移动计算中节约电量的动态程序分割算法[J]. 计算机应用, 2012, 32(12): 3295-3298.
[7]	李伟葛洪伟纪鹏. 不均匀网络中的局域搜索免疫[J]. 计算机应用, 2011, 31(01): 135-138.
[8]	纪鹏葛洪伟. 删除边的免疫策略[J]. 计算机应用, 2010, 30(07): 1775-1777.
[9]	纪鹏葛洪伟. 基于富人俱乐部特性的搜索免疫[J]. 计算机应用, 2010, 30(06): 1533-1535.
[10]	张金增范明. 一种改进的基于最大流的Web社区挖掘算法[J]. 计算机应用, 2009, 29(1): 213-216.
[11]	厍向阳罗晓霞. 点和边有容量约束的网络最大流新算法[J]. 计算机应用, 2008, 28(1): 143-145.