- 期刊
A parallel algorithm for the maximum flow problem
摘要
The maximum flow problem is an important research field in graph theory, and it has a wide range of applications in urban traffic flow, network planning and other fields. There are many approaches to solve the maximum flow problem, but there are still some shortcomings. To solve the problem of high computational complexity of the maximum flow algorithm, a parallel maximum flow algorithm is proposed which divides the original graph into overlay graph and subgraphs. The experiments in TIGER/Line show that the maximum flow result calculated by the algorithm in this paper is consistent with that of the Edmonds-Karp algorithm, the proposed algorithm significantly reduces the calculation time and the time complexity.
參考文獻
Min, Wang , Q. Yongsheng and W. Shoubao. "Algorithm of urban traffic network capacity based on virtual vertices max-flow." Computer Engineering & Applications 46.11(2010):243-245.
Yi Chen, X. X, et al. "Large-Scale Resource Scheduling Based on Minimum Cost Maximum Flow." Journal of Software (2017).
Sato, Masatoshi , et al. "Image Segmentation Using Graph Cuts Based on Maximum-Flow Neural Network." International Conference on Neural Information Processing 2016.
Liang, Chengchao, F. R. Yu and X. Zhang. "Information-centric network function virtualization over 5g mobile wireless networks." IEEE Network 29.3(2015):68-74.
Madry, Aleksander. "Computing Maximum Flow with Augmenting Electrical Flows." (2016).
延伸閱讀
- Cheng, C. H. (2006). Efficient Algorithms for Some Variants of the Maximum-Sum Segment Problem [master's thesis, National Taiwan University]. Airiti Library. https://doi.org/10.6342/NTU.2006.01698
- Dang, Y. Z., & Gao, Y. (2012). An Extrapolated Iterative Algorithm for Multiple-Set Split Feasibility Problem. Abstract and Applied Analysis, 2012(), 606-617. https://doi.org/10.1155/2012/149508
- Miau, C. A. (2012). An Exact Algorithm for the Maximum Induced Matching Problem [master's thesis, National Chung Cheng University]. Airiti Library. https://www.airitilibrary.com/Article/Detail?DocID=U0033-2110201613521653
- ADDOU, A., & BENAHMED, A. (2005). PARALLEL SYNCHRONOUS ALGORITHM FOR NONLINEAR FIXED POINT PROBLEMS. International Journal of Mathematics and Mathematical Sciences, 2005(), 3175-3183-257. https://doi.org/10.1155/IJMMS.2005.3175
- Wu, P. C. (2014). An Evaluation of Maximum Flow Algorithms in Distributed-Parallel Environment [master's thesis, National Tsing Hua University]. Airiti Library. https://doi.org/10.6843/NTHU.2014.00494