[1]张柏礼,王媛瑗,洪亮,等.动态网络中最大流快速增量求解[J].东南大学学报(自然科学版),2017,47(3):450-455.[doi:10.3969/j.issn.1001-0505.2017.03.006]
 Zhang Baili,Wang Yuanyuan,Hong Liang,et al.Fast incremental maximum flow algorithm in dynamic network[J].Journal of Southeast University (Natural Science Edition),2017,47(3):450-455.[doi:10.3969/j.issn.1001-0505.2017.03.006]
点击复制

动态网络中最大流快速增量求解()
分享到:

《东南大学学报(自然科学版)》[ISSN:1001-0505/CN:32-1178/N]

卷:
47
期数:
2017年第3期
页码:
450-455
栏目:
计算机科学与工程
出版日期:
2017-05-20

文章信息/Info

Title:
Fast incremental maximum flow algorithm in dynamic network
作者:
张柏礼12王媛瑗1洪亮3田伟4吕建华1 2
1东南大学计算机科学与工程学院, 南京 211189; 2东南大学计算机网络和信息集成教育部重点实验室, 南京 211189; 3中国能源研究会电力安全与应急技术中心, 北京 100045; 4南京弘毅电气自动化有限公司, 南京 210039
Author(s):
Zhang Baili12 Wang Yuanyuan1 Hong Liang3 Tian Wei4 Lü Jianhua12
1School of Computer Science and Engineering, Southeast University, Nanjing 211189, China
2Key Laboratory of Computer Network and Information Integration of Ministry of Education, Southeast University, Nanjing 211189, China
3 Electrical Power Industry Security and Emergency Response Technology Center, China Energy Research Society, Beijing 100045, China
4Nanjing Hongyi Electric Automation Technology Co., Ltd., Nanjing 210039, China
关键词:
最大流 增量算法 增广路径选择树 简单路径
Keywords:
maximum flow incremental algorithm augmented routing tree simple path
分类号:
TP301.6;TP393
DOI:
10.3969/j.issn.1001-0505.2017.03.006
摘要:
利用损毁网络与原网络的结构包含性,提出了一种基于增广路径选择树的最大流增量算法MFIA-ART.算法在原网络最大流的求解过程中,对简单路径集等相关的中间结果给予缓存,构成增广路径候选集,当网络拓扑改变时直接在其中查找有效的增广路径,无需对新的残余网络进行复杂计算. 同时为了避免遍历包含饱和边的简单路径,进一步利用增广路径选择树ART来组织所有可能的增广路径集,从而可以通过一条从根节点到某个叶节点的路径找到所有需要的增广路径,获得最大流量.其遍历的深度为ART树的高度H,远小于所有增广路径的数量,因而显著地提高了求解最大流的效率.实验结果表明,MFIA-ART相对于采用经典的Dinic算法重新计算最大流的方法,在时间性能方面有数量级的提高,尤其适合应用于简单路径数量较少的稀疏性网络.
Abstract:
An maximum flow incremental algorithm based on augmented routing tree(MFIA-ART)was proposed to obtain augmenting paths directly without complex calculation. The algorithm cached the simple path information during calculating the original network maximum flow. When network topology changing, the augmenting path was obtained from the cache data, rather than through complex calculation in residual network. In addition, to avoid traversing invalid simple paths including saturated edges, an augmented routing tree was proposed to index all simple paths. Using the tree, the next augmenting paths could be sequentially found by traversing from root to leaf to achieve maximum flow. The time complexity is determined by the height of ART, it was far less than the augmenting path number thus improving the algorithm performance. Experimental results show that MFIA-ART in time performance has a greater advantage than Dinic algorithm, and it is especially suitable for sparse graph.

参考文献/References:

[1] Goldberg A V. Recent developments in maximum flow algorithms(invited lecture)[C]//Proceedings of the 6th Scandinavian Workshop on Algorithm Theory.Heidelber: Springer-Verlags, 1988:1-10.
[2] Cormen T H, Leiserson C E, Rivest R L, et al. Introduction to algorithms[M]. 2nd ed. Cambridge: MIT Press, 2001:588-760.
[3] Ahuja R K, Magnanti T L, Orlin J B. Network flows: Theory, algorithms and applications[M]. Upper Saddle River, NJ, USA: Prentice Hall Press, 2005:294-356.
[4] Ford L R, Fulkerson D R. Flows in networks[M]. Princeton, USA: Princeton University Press, 1962:1-96.
[5] Edmonds J, Karp R M. Theoretical improvements in algorithm efficiency for networks flow problems[J]. Journal of the ACM, 1972, 19(2):248-264. DOI:10.1145/321694.321699.
[6] Goldberg A V, Rao S. Beyond the flow decomposition barrier[J]. Journal of the ACM, 1998, 45(5):783-797. DOI:10.1145/290179.290181.
[7] 张宪超, 万颖瑜, 陈国良. 一类实际网络中的最小截算法[J]. 软件学报, 2003,14(5):885-890.
  Zhang Xianchao, Wan Yingyu, Chen Guoliang. Approaches to the minimum cut problem in a class of practical networks[J]. Journal of Software, 2003, 14(5): 885-890.(in Chinese)
[8] 张宪超, 江贺, 陈国良. 节点和边都有容量的有向平面网络中的最小截和最大流[J]. 计算机学报, 2006,29(4):543-551.
  Zhang Xianchao, Jiang He, Chen Guoliang. Minimum cuts and maximum flows in directed planar networks with both node and edge capacities[J]. Chinese Journal of Computers, 2006, 29(4):543-551.(in Chinese)
[9] Lee Y T, Rao S, Srivastava N. A new approach to computing maximum flows using electrical flows[C]//Proceedings of the 45th Annual ACM Symposium on Theory of Computing. Palo Alto, CA, USA, 2013:755-764. DOI:10.1145/2488608.2488704.
[10] Daitch S I, Spielman D A. Faster approximate lossy generalized flow via interior point algorithms[C]//Proceedings of the 40th Annual ACM Symposium on Theory of Computing. Victoria, BC, Canada, 2008:451-460. DOI:10.1145/1374376.1374441.
[11] Peng R. Approximate undirected maximum flows in O(Mpolylog(n))time[C]//Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms. Arlington, VA, USA, 2016:1862-1867. DOI:10.1137/1.9781611974331.ch130.
[12] Zhao S, Xu X S, Hua B. Contraction network for solving maximum flow problem[C]//Proceedings of the ACM SIGKDD Workshop on Mining Data Semantics. Beijing, China, 2012:1-6. DOI:10.1145/2350190.2350198.
[13] Sharma M, Ghosh D. Speeding up the estimation of the expected value of maximum flow through reliable networks[J]. IEEE Transactions on Reliability, 2013, 62(1):105-115. DOI:10.1109/tr.2013.2241132.
[14] Hadji M, Zeghlache D. Minimum cost maximum flow algorithm for dynamic resource allocation in clouds[C]//IEEE International Conference on Cloud Computing. Honolulu, Hawaii, USA, 2012:876-882. DOI:10.1109/cloud.2012.36.
[15] Szymanski T H. Achieving minimum-routing-cost maximum-flows in infrastructure wireless mesh networks[C]//IEEE Wireless Communications & Networking Conference. Paris, France, 2012:2031-2036. DOI:10.1109/wcnc.2012.6214124.
[16] Bora N, Arora S, Arora N. An efficient algorithm for calculating maximum bipartite matching in a graph[J]. International Journal of Advanced Computer Research, 2013, 3(10):193-199.
[17] Gu T L, Chang L, Xu Z B. A novel symbolic algorithm for mximum weighted matching in bipartite graphs[J]. International Journal of Comunications, Network and System Sciences, 2012, 4(2):111-121. DOI:10.4236/ijcns.2011.42014.
[18] Zhao P X, Zhang X. A survey on reliability evaluation of stochastic-flow networks in terms of minimal paths[C]//International Conference on Information Engineering & Computer Science. Wuhan, China, 2009:2010-2013. DOI:10.1109/iciecs.2009.5365424.
[19] Jane C C, Lin J S, Yuan J. Reliability evaluation of a limited-flow network in terms of minimal cutsets[J]. IEEE Transactions on Reliability, 1993, 42(3): 354-361, 368. DOI:10.1109/24.257817.
[20] 蔡伟, 张柏礼, 吕建华. 不确定图最可靠最大流算法研究[J].计算机学报, 2012, 35(11):2371-2380. DOI:10.3724/SP.J.1016.2012.02371.
Cai Wei, Zhang Baili, Lü Jianhua. Algorithms of the most reliable maximum flow on uncertain graph[J].Chinese Journal of Computers, 2012, 35(11): 2371-2380. DOI:10.3724/SP.J.1016.2012.02371. (in Chinese)
[21] 张铃. 动态网络上最大流概念及其性质的研究[J]. 模式识别与人工智能, 2013,26(7):609-614. DOI:10.3969/j.issn.1003-6059.2013.07.001.
Zhang Ling. The concept of max-flow and its properties in dynamic networks[J]. Pattern Recognition and Artificial Intelligence, 2013, 26(7):609-614. DOI:10.3969/j.issn.1003-6059.2013.07.001. (in Chinese)
[22] Kas M, Wachs M, Carley K M, et al. Incremental algorithm for updating betweenness centrality in dynamically growing networks[C]//International Conference on Advances in Social Networks Analysis & Mining. Niagara Falls, Canada, 2013:33-40. DOI:10.1145/2492517.2492533.
[23] Ben-Eliyahu-Zohary R. An incremental algorithm for generating all minimal models[J]. Artificial Intelligence, 2005, 169(1): 1-22. DOI:10.1016/j.artint.2005.06.003.
[24] Hsieh M C, Lee Y S, Yen S J. An efficient incremental algorithm for mining Web traversal patterns[C]//IEEE International Conference on E-business. Beijing, China, 2005:274-281.
[25] Klingman D, Napier A, Stutz J. NETNEN:A program for generating large scale capacitated assignment, transportation and minimal cost flow network problems[J]. Management Science, 1974, 20(5):814-821. DOI:10.1287/mnsc.20.5.814.
[26] Johnson D B. Finding all the elementary circuits of a directed graph[J]. SIAM Journal on Computing, 1975, 4(1):77-84. DOI:10.1137/0204007.

备注/Memo

备注/Memo:
收稿日期: 2016-09-05.
作者简介: 张柏礼(1970—),男,博士,副教授,bailey_zhang@163.com.
基金项目: 国家自然科学基金资助项目(61300200,61232007,61073059).
引用本文: 张柏礼,王媛瑗,洪亮,等.动态网络中最大流快速增量求解[J].东南大学学报(自然科学版),2017,47(3):450-455. DOI:10.3969/j.issn.1001-0505.2017.03.006.
更新日期/Last Update: 2017-05-20