[1] DANG Yaoguo, HUANG Jinxin, DING Xiaoyu, WANG Junjie, et al. Novel two‑stage preflow algorithm for solving the maximum flow problem in a network with circles [J]. Journal of Southeast University (English Edition), 2025, 41 (1): 91-100. [doi:10.3969/j.issn.1003-7985.2025.01.012]
Copy
Novel two‑stage preflow algorithm for solving the maximum flow problem in a network with circles(
)
两阶段预流算法构建及其在带环网络最大流中的应用
)Journal of Southeast University (English Edition)[ISSN:1003-7985/CN:32-1325/N]
- Volumn:
- 41
- Issue:
- 2025 1
- Page:
- 91-100
- Research Field:
- Mathematics, Physics, Mechanics
- Publishing date:
- 2025-03-07
Info
- Title:
- Novel two‑stage preflow algorithm for solving the maximum flow problem in a network with circles
- 两阶段预流算法构建及其在带环网络最大流中的应用
- Author(s):
- DANG Yaoguo; HUANG Jinxin; DING Xiaoyu; WANG Junjie
- College of Economics and Management, Nanjing University of Aeronautics and Astronautics, Nanjing 211100, China
- PACS:
- O22;O157.5
- DOI:
- 10.3969/j.issn.1003-7985.2025.01.012
- Abstract:
- The presence of circles in the network maximum flow problem increases the complexity of the preflow algorithm. This study proposes a novel two‑stage preflow algorithm to address this issue. First, this study proves that at least one zero‑flow arc must be present when the flow of the network reaches its maximum value. This result indicates that the maximum flow of the network will remain constant if a zero‑flow arc within a circle is removed; therefore, the maximum flow of each network without circles can be calculated. The first stage involves identifying the zero‑flow arc in the circle when the network flow reaches its maximum. The second stage aims to remove the zero‑flow arc identified and modified in the first stage, thereby producing a new network without circles. The maximum flow of the original looped network can be obtained by solving the maximum flow of the newly generated acyclic network. Finally, an example is provided to demonstrate the validity and feasibility of this algorithm. This algorithm not only improves computational efficiency but also provides new perspectives and tools for solving similar network optimization problems.
- 在处理带环网络的最大流问题时，为了降低算法的复杂度，提出了一种新颖的两阶段预流算法。首先，证明了当网络达到最大流状态时，环中必然存在至少一条最小可能流等于零的弧。在环中，如果每条弧同时获得最小可能流量，在移除任意一条弧之后，环中原始零流弧保持不变。其次，构建了使带环网络转换为无环网络两阶段预流算法：阶段1为当网络达到最大流时标记出环中的零流弧；阶段2为去除在阶段1中找到的零流弧，从而将原本的带环网络转化为无环网络。通过求解新生成的无环网络的最大流，可以得到原始带环网络的最大流解。最后，通过实例验证了该算法的有效性和可行性。该算法不仅提高了计算效率，还为解决类似网络优化问题提供了新的视角和工具。
References:
[1]CAO B, ZHAO J W, GU Y, et al. Security‑aware industrial wireless sensor network deployment optimization[J]. IEEE Transactions on Industrial Informatics, 2020, 16(8): 5309‑5316.
[2]ZHANG L, FENG D M, WU G. Vehicle dynamic load recognition method based on LSTM network[J]. Journal of Southeast University (Natural Science Edition), 2023, 53(2): 187‑192. (in Chinese)
[3]GUPTA S P, PYAKUREL U, DHAMALA T N. Multi‑commodity flow problem on lossy network with partial lane reversals[J]. Annals of Operations Research, 2023, 323(1): 45‑63.
[4]MIRZAEI M, MIRZAPOUR AL‑E‑HASHEM S M J, AKBARPOUR SHIRAZI M. A maximum‑flow network interdiction problem in an uncertain environment under information asymmetry condition: Application to smuggling goods[J]. Computers & Industrial Engineering, 2021, 162: 107708.
[5]DING J, WEN C Y, LI G Q, et al. Target controllability in multilayer networks via minimum‑cost maximum⁃flow method[J]. IEEE Transactions on Neural Networks and Learning Systems, 2021, 32(5): 1949‑1962.
[6]XIE C Y, DONG L. Graph‑enhanced neural interactive collaborative filtering[J]. Journal of Southeast University (English Edition), 2022, 38(2): 110‑117.
[7]MEHRYAR M, HAFEZALKOTOB A, AZIZI A, et al. Cooperative reliability allocation in network flow problems considering greenhouse gas emissions: Optical fiber networks structure[J]. Journal of Cleaner Production, 2021, 326: 129315.
[8]SHI M Z, LIN Z D. Effectiveness evaluation of railway traffic safety based on the DEMATEL, AHP, and ANP methods[J]. Journal of Southeast University (English Edition), 2023, 39(2): 133‑141.
[9]ALIPOUR H, MUÑOZ M A, SMITH‑MILES K. Enhanced instance space analysis for the maximum flow problem[J]. European Journal of Operational Research, 2023, 304(2): 411‑428.
[10]FORD L R Jr, FULKERSON D R. A simple algorithm for finding maximal network flows and an application to the Hitchcock problem[J]. Canadian Journal of Mathematics, 1957, 9: 210‑218.
[11]AHUJA R K, ORLIN J B. A fast and simple algorithm for the maximum flow problem[J]. Operations Research, 1989, 37(5): 748‑759.
[12]HUANG D H. A network reliability algorithm for a stochastic flow network with non‑conservation flow[J]. Reliability Engineering & System Safety, 2023, 240: 109584.
[13]KARZANOV A. Determining the maximal flow in a network by the method of preflows[J]. Doklady Mathematics, 1974, 15: 434‑437.
[14]KARA G, ÖZTURAN C. Algorithm 1002: Graph coloring based parallel push‑relabel algorithm for the maximum flow problem[J]. ACM Transactions on Mathematical Software, 2019, 45(4): 1‑28.
[15]DEUTSCH M, DAĞDELEN K, JOHNSON T. An open‑source program for efficiently computing ultimate pit limits: MineFlow[J]. Natural Resources Research, 2022, 31(3): 1175‑1187.
[16]HOLZHAUSER M, KRUMKE S O, THIELEN C. A network simplex method for the budget‑constrained minimum cost flow problem[J]. European Journal of Operational Research, 2017, 259(3): 864‑872.
[17]LI X L, WANG Y Q, MA G B, et al. Electric load forecasting based on long‑short‑term‑memory network via simplex optimizer during COVID‑19[J]. Energy Reports, 2022, 8: 1‑12.
[18]HUANG R, FENG M R, CHEN Z J, et al. Exploring network reliability by predicting link status based on simplex neural network[J]. Displays, 2023, 79: 102457.
[19]APAOLAZA I, VALCARCEL L V, PLANES F J. gMCS: Fast computation of genetic minimal cut sets in large networks[J]. Bioinformatics, 2019, 35(3): 535‑537.
[20]MIRASKARSHAHI R, ZABETI H, STEPHEN T, et al. MCS2: Minimal coordinated supports for fast enumeration of minimal cut sets in metabolic networks[J]. Bioinformatics, 2019, 35(14): i615‑i623.
[21]MATHEW S, MORDESON J N. Directed fuzzy networks as a model to illicit flows and max flow Min cut theorem[J]. New Mathematics and Natural Computation, 2017, 13(3): 219‑229.
[22]ZHU H X, SHEN J, SU Z G, et al. RBF neural network regression model based on fuzzy observations [J]. Journal of Southeast University (English Edition), 2013, 29(4): 400‑406.
[23]ZHANG R Q, WEI W. A parallel algorithm for the maximum flow problem[J]. International Core Journal of Engineering, 2019, 5: 61‑64.
[24]BERTSIMAS D, STELLATO B. The voice of optimization[J]. Machine Learning, 2021, 110(2): 249‑277.
[25]BAYCIK N O. Machine learning based approaches to solve the maximum flow network interdiction problem[J]. Computers & Industrial Engineering, 2022, 167: 107873.
[26]ZHANG L, LU J, LEI D. Vulnerability analysis of bus‑metro composite network based on complex network and spatial information embedding[J]. Journal of Southeast University (Natural Science Edition), 2019, 49(4): 773‑780.(in Chinese)
[27]WANG J J, CAI Y, FENG Y, et al. Novel grey dynamic trend relational analysis models with different types of accumulation delay effects for time‑delay systems[J]. Expert Systems with Applications, 2024, 238: 121661.
[28]WU J S, CHEN N, ZHOU C J, et al. Computing the number of loop‑free k‑hop paths of networks[J]. IEEE Transactions on Services Computing, 2022, 15(4): 2114‑2128.
[29]WILLSON S J. Merging arcs to produce acyclic phylogenetic networks and normal networks[J]. Bulletin of Mathematical Biology, 2022, 84(2): 26.
[30]WU Y, YANG Y L, LIU S Y. The network maximum flow based on the flow matrix[J]. System Engineering, 2007, 25(10): 122‑125.
Memo
- Memo:
-
Received 2024-08-02,Revised 2024-10-08.
Biography:Dang Yaoguo (1964—), male, doctor, professor, iamdangyg@163.com.
Foundation items:The National Natural Science Foundation of China (No.72001107, 72271120), the Fundamental Research Funds for the Central Universities (No. NS2024047, NP2024106), the China Postdoctoral Science Foundation (No. 2020T130297, 2019M660119).
Citation:DANG Yaoguo,HUANG Jinxin,DING Xiaoyu,et al.Novel two-stage preflow algorithm for solving the maximum flow problem in a network with circles[J].Journal of Southeast University (English Edition),2025,41(1):91-100.DOI:10.3969/j.issn.1003-7985.2025. 01.012.DOI:10.3969/j.issn.1003-7985.2025.01.012