论文:2018,Vol:36,Issue(5):955-962
引用本文:
刘扬, 魏蔚, 许贺洋. 基于双连通分量覆盖图的稀疏大图最大流并行加速方法[J]. 西北工业大学学报
Liu Yang, Wei Wei, Xu Heyang. Engineering Bi-Connected Component Overlay for Maximum-Flow Parallel Acceleration in Large Sparse Graph[J]. Northwestern polytechnical university

基于双连通分量覆盖图的稀疏大图最大流并行加速方法
刘扬, 魏蔚, 许贺洋
河南工业大学 信息科学与工程学院, 河南 郑州 450001
摘要:
最大流问题是图论中重要的基础性问题,大规模网络中的最大流加速已成为重要研究方向,已有工作包括并行计算加速和图缩减加速2种思路,但仍有较大改进空间:①图缩减和并行计算2种加速思路并未充分融合,导致各自加速效果受限;②已有加速算法对常见的多次最大流求解支持不足,导致多次计算间存在大量冗余工作;③已有加速算法往往需涉及出入度和边容量等多个条件,计算复杂度偏高。针对上述问题,提出了一种基于优化子图的最大流并行加速方法,通过识别原始大图的双连通分量并建立覆盖图,可将任意最大流问题分解为独立的子问题,并行求解快速获取最大流精确解;覆盖图的构建仅涉及节点之间连接关系,具较低的时间复杂度。在基准图上的测试结果表明,算法可显著缩短稀疏大图中最大流计算时间。
关键词:    计算复杂度    图理论    最大流问题    稀疏图计算    双联通分量    覆盖图    并行计算   
Engineering Bi-Connected Component Overlay for Maximum-Flow Parallel Acceleration in Large Sparse Graph
Liu Yang, Wei Wei, Xu Heyang
College of Information Science and Engineering, Henan University of Technology, Zhengzhou 450001, China
Abstract:
Network maximum flow problem is important and basic in graph theory, and one of its research directions is maximum-flow acceleration in large-scale graph. Existing acceleration strategy includes graph contraction and parallel computation, where there is still room for improvement:(1) The existing two acceleration strategies are not fully integrated, leading to their limited acceleration effect; (2) There is no sufficient support for computing multiple maximum-flow in one graph, leading to a lot of redundant computation. (3)The existing preprocessing methods need to consider node degrees and capacity constraints, resulting in high computational complexity. To address above problems, we identify the bi-connected components in a given graph and build an overlay, which can help split the maximum-flow problem into several subproblems and then solve them in parallel. The algorithm only uses the connectivity in the graph and has low complexity. The analyses and experiments on benchmark graphs indicate that the method can significantly shorten the calculation time in large sparse graphs.
Key words:    computational complexity    graph theory    maximum flow problem    sparse graph computing    bi-connected component    overlay    parallel computing   
收稿日期: 2017-09-06     修回日期:
DOI:
基金项目: 国家自然科学基金(61472460,U1504607,61702162)、河南省高校科技创新团队支持计划(17IRTSTHN011)、河南省教育厅科学技术研究重点项目(17A520004)、粮食信息处理与控制教育部重点实验室开放基金课题(KFJJ-2016-104)、河南省科技厅科技攻关项目(172102110013)、河南工业大学高层次人才基金(2017025)、河南工业大学校骨干教师(2012012)及河南工业大学校基金(2018RCJH07,2018QNJH26)资助
通讯作者:     Email:
作者简介: 刘扬(1978-),女,河南工业大学副教授、博士,主要从事分布式计算及图计算研究。
相关功能
PDF(1572KB) Free
打印本文
把本文推荐给朋友
作者相关文章
刘扬  在本刊中的所有文章
魏蔚  在本刊中的所有文章
许贺洋  在本刊中的所有文章

参考文献:
[1] Goldberg A, Tarjan E. Efficient Maximum Flow Algorithms[J]. Communications of the ACM, 2014, 57(8):82-89
[2] Liang C, Yu F R, Zhang X. Information-Centric Network Function Virtualization over 5g Mobile Wireless Networks[J]. IEEE Network, 2015, 29(3):68-74
[3] Kosut O. Max-Flow Min-Cut for Power System Security Index Computation[C]//IEEE Sensor Array and Multichannel Signal Processing Workshop, 2015:61-64
[4] 陈晓旭, 吴恒, 吴悦文. 基于最小费用最大流的大规模资源调度方法[J]. 软件学报, 2017, 28(3):598-610 Chen Xiaoxu, Wu Heng, Wu Yuewen. Large-Scale Resource Scheduling Based on Minimum Cost Maximum Flow[J]. Journal of Software, 2017, 28(3):598-610(in Chinese)
[5] Ford L R, Fulkerson D R. Notes on Linear Programming, Part Ⅱ:Maximal Flow through a Network[M]. Santa Monica, RAND Corporation, 1977:16-31
[6] Karzanov A V. Determining the Maximal Flow in a Network by the Method of Preflows[J]. Doklady Mathematics, 1974, 15(1):434-437
[7] Schiopu C, Ciurea E. The Maximum Flows in Planar Dynamic Networks[J]. International Journal of Computers Communications & Control, 2016, 11(2):282-291
[8] Goldberg AV, Hed S, Kaplan H, Tarjan RE, Werneck RF. Maximum Flows by Incremental Breadth-First Search[C]//European Symposium on Algorithms, 2011:457-468
[9] Ghaffari M, Karrenbauer A, Kuhn F. Near-Optimal Distributed Maximum Flow:Extended Abstract[C]//ACM Symposium on Principles of Distributed Computing, 2015:81-90
[10] Sherman J. Nearly Maximum Flows in Nearly Linear Time[C]//IEEE Symposium on Foundations of Computer Science, 2013:263-269
[11] Liers F, Pardella G. Simplifying Maximum Flow Computations:The Effect of Shrinking and Good Initial Flows[J]. Discrete Applied Mathematics, 2011, 159(17):2187-2203
[12] Dan G. Very Simple Methods for All Pairs Network Flow Analysis[J]. Siam Journal on Computing, 1990, 19(1):143-155
[13] Zhang Y, Xu X, Hua B. Contracting Community for Computing Maximum Flow[C]//IEEE International Conference on Granular Computing, 2012:651-656
[14] Zhang Y P, Hua B, Jiang J, et al. Research on the Maximum Flow in Large-Scale Network[C]//International Conference on Computational Intelligence and Security(CIS), 2011:482-486
[15] Scheuermann B, Rosenhahn B. Slimcuts:Graphcuts for High Resolution Images Using Graph Reduction[C]//International Workshop on Energy Minimization Methods in Computer Vision and Pattern Recognition, 2011:219-232
[16] Zhen C, Zhang L. The Computation of Maximum Flow in Network Analysis Based on Quotient Space Theory[J]. Chinese Journal of Computers, 2015, 38(8):1705-1712
[17] Niklas B, Blelloch G, Shun J. Efficient Implementation of a Synchronous Parallel Push-Relabel Algorithm[C]//European Symposia on Algorithms, 2015:106-117
[18] Soner S, Ozturan C. Experiences with Parallel Multi-Threaded Network Maximum Flow Algorithm[J]. Partnership for Advanced Computing in Europe, 2013, 2013(1):1-10
[19] Benoit D, Dupont E, Zhang W. Distributed Max-Flow in Spark[EB/OL]. (2015-06-03)[2017-04-06]. http://stanford.edu/~rezab/classes/cme323/S15/projects/distributed_max_flow_report.pdf
[20] Halim F, Yap R, Wu Y. A Mapreduce-Based Maximum-Flow Algorithm for Large Small-World Network Graphs[C]//International Conference on Distributed Computing Systems(ICDCS), 2011:192-202
[21] Goldfarb D, Grigoriadis M D. A Computational Comparison of the Dinic and Network Simplex Methods for Maximum Flow[J]. Annals of Operations Research, 1988, 13(1):81-123
[22] Goldberg, A V. Two-Level Push-Relabel Algorithm for the Maximum Flow Problem[C]//The Fifth Conference on Algorithmic Aspects in Information Management, 2009:212-225