Novel two-stage preflow algorithm for solving the maximum flow problem in a network with circles; [两阶段预流算法构建及其在带环网络最大流中的应用]

被引：0

作者：

Dang, Yaoguo ^{[1
]}

Huang, Jinxin ^{[1
]}

Ding, Xiaoyu ^{[1
]}

Wang, Junjie ^{[1
]}

机构：

[1] College of Economics and Management, Nanjing University of Aeronautics and Astronautics, Nanjing

来源：

Journal of Southeast University (English Edition) | 2025年 / 41卷 / 01期

基金：

中国国家自然科学基金; 中国博士后科学基金;

关键词：

maximum flow; network with circles; two-stage preflow algorithm; zero-flow arc;

D O I：

10.3969/j.issn.1003-7985.2025.01.012

中图分类号：

学科分类号：

摘要：

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. © 2025 Southeast University. All rights reserved.

引用

页码：91 / 100

页数：9

共 30 条

[1]

CAO B, ZHAO J W, GU Y, Et al., Security-aware industrial wireless sensor network deployment optimization [J], IEEE Transactions on Industrial Informatics, 16, 8, pp. 5309-5316, (2020)

[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), 53, 2, pp. 187-192, (2023)

[3]

GUPTA S P, PYAKUREL U, DHAMALA T N., Multi-commodity flow problem on lossy network with partial lane reversals, Annals of Operations Research, 323, 1, pp. 45-63, (2023)

[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, 162, (2021)

[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, 32, 5, pp. 1949-1962, (2021)

[6]

XIE C Y, DONG L., Graph-enhanced neural interactive collaborative filtering[J], Journal of Southeast University(English Edition), 38, 2, pp. 110-117, (2022)

[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, 326, (2021)

[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), 39, 2, pp. 133-141, (2023)

[9]

ALIPOUR H, MUNOZ M A, SMITH-MILES K., Enhanced instance space analysis for the maximum flow problem, European Journal of Operational Research, 304, 2, pp. 411-428, (2023)

[10]

FORD L R, FULKERSON D R., A simple algorithm for finding maximal network flows and an application to the Hitchcock problem[J], Canadian Journal of Mathematics, 9, pp. 210-218, (1957)

← 1 2 3 →