Improved algorithm for vital arc of maximum dynamic flow

doi:10.11772/j.issn.1001-9081.2014.04.0969

Journal of Computer Applications ›› 2014, Vol. 34 ›› Issue (4): 969-972.DOI: 10.11772/j.issn.1001-9081.2014.04.0969

• Network and communications • Previous Articles Next Articles

Improved algorithm for vital arc of maximum dynamic flow

LIU Yangyang,XIE Zheng,CHEN Zhi

College of Science, National University of Defense Technology, Changsha Hunan 410073, China

Received:2013-10-21 Revised:2013-12-26 Online:2014-04-29 Published:2014-04-01
Contact: LIU Yangyang

最大动态流关键弧的改进算法

刘杨杨,谢政,陈挚

国防科学技术大学理学院,长沙 410073

通讯作者: 刘杨杨
作者简介:刘杨杨(1990-),男,湖北襄阳人,硕士研究生,主要研究方向:网络最优化;
谢政(1960-),男,湖南衡阳人,教授,主要研究方向:网络最优化;
陈挚(1965-),男,湖南湘乡人,副教授,主要研究方向:网络最优化。

Abstract

Abstract:

For the vital arc problem of maximum dynamic flow in time-capacitated network, the classic Ford-Fulkerson maximum dynamic flow algorithm was analyzed and simplified. Thus an improved algorithm based on minimum cost augmenting path to find the vital arc of the maximum dynamic flow was proposed. The shared minimum augmenting paths were retained when computing maximum dynamic flow in new network and the unnecessary computation was removed in the algorithm. Finally, the improved algorithm was compared with the original algorithm and natural algorithm. The numerical analysis shows that the improved algorithm is more efficient than the natural algorithm

摘要：

针对时间容量网络的最大动态流的关键弧问题，首先分析了经典的Ford-Fulkerson最大动态流算法，在此基础上简化了最大动态流算法，并由此提出一个基于最小费用增广路来寻找最大动态流关键弧的改进算法。算法将计算新网络最大动态流时共有的最小费用路保留，去掉了自然算法中重复的计算。的效率更高。

CLC Number:

TP301.6

LIU Yangyang XIE Zheng CHEN Zhi. Improved algorithm for vital arc of maximum dynamic flow[J]. Journal of Computer Applications, 2014, 34(4): 969-972.

刘杨杨谢政陈挚. 最大动态流关键弧的改进算法[J]. 计算机应用, 2014, 34(4): 969-972.

References

［1］AHUJIA R K, MAGNANTI T L, ORLIN J B. Network flows: theory algorithms and application ［M］. Upper Saddle River: Prentice Hall, 1993.
［2］FORD L R, FULKERSON D R. Constructing maximal dynamic flows from static flows ［J］. Operations Research, 1958, 6(3): 419-433.
［3］PICARD J-C, QUEYARANNE M. On the structure of all minimum cut in a network and applications ［C］// Combinatorial Optimization II: Mathematical Programming Studies. Berlin: Springer-Verlag, 1980: 8-16.
［4］RAD M A, KAKHKI H T. Maximum dynamic network flow interdiction problem: new formulation and solution procedures ［J］. Computers & Industrial Engineering, 2013, 65(4): 531-536.
［5］LUNDAY B J, SHERALI H D. A dynamic network interdiction problem ［J］. Informatica, 2010, 21(4): 553-574.
［6］ROYSET J O, WOOD R K. Solving the bi-objective maximum flow network-interdiction problem ［J］. INFORMS Journal on Computing, 2007, 19(2): 175-184.
［7］ANEJA Y P, CHANDRASEKARAN R, NAIR K P K. Maximizing residual flow under an arc destruction ［J］. Networks, 2001, 38 (4): 194-198.
［8］DU D, CHANDRASEKARAN R. The maximum residual flow problem: NP-hardness with two arc destruction ［J］. Networks, 2007, 50(3): 181-182.
［9］TAHMASBI R, NASRABADI E, HASHEMI S M. The value of information in stochastic maximum flow problems ［J］. Computers & Operations Research, 2013, 40(7): 1744-1751.
［10］SKUTELLA M. An introduction to network flows over time ［C］// Research Trends in Combinatorial Optimization. Berlin: Springer-Verlag, 2009: 451-482.
［11］XIE Z. Theory of network algorithm and complexity ［M］. 2nd ed. Changsha: National University of Defense Technology Press, 2003. (谢政.网络算法与复杂性理论［M］.2版.长沙:国防科技大学出版社,2003.
［12］ZHANG L. The concept of maximum flow and its properties in dynamic networks ［J］. Pattern Recognition and Artificial Intelligence, 2013, 26(7):609-614. (张铃.动态网络上最大流概念及其性质的研究［J］.模式识别与人工智能,2013,26(7):609-614.)
［13］STRANG G. Maximum flows and minimum cuts in the plane ［J］. Journal of Global Optimization, 2010, 47(3): 527-535.

[1]	. YOLOv5s-MRD: an efficient fire and smoke detection algorithm for complex scenarios based on YOLOv5s [J]. Journal of Computer Applications, 0, (): 0-0.
[2]	Qiye ZHANG, Xinrui ZENG. Efficient active-set method for support vector data description problem with Gaussian kernel [J]. Journal of Computer Applications, 2024, 44(12): 3808-3814.
[3]	. Path planning of multi-UAV formation based on improved artificial potential field method [J]. Journal of Computer Applications, 0, (): 0-0.
[4]	. Dual-population dual-stage evolutionary algorithm for complex constrained multi-objective optimization problems [J]. Journal of Computer Applications, 0, (): 0-0.
[5]	Qin LENG, Zhengyuan MAO. Two echelon location-routing optimization considering facility sizing decision [J]. Journal of Computer Applications, 2024, 44(11): 3513-3520.
[6]	Qingyuan PENG, Xiaofeng WANG, Junxia WANG, Yingying HUA, Ao TANG, Fei HE. Review of phase transition in satisfiability problems [J]. Journal of Computer Applications, 2024, 44(11): 3503-3512.
[7]	Renke SUN, Zhiyu HUANGFU, Hu CHEN, Zhongnian LI, Xinzheng XU. Survey of neural architecture search [J]. Journal of Computer Applications, 2024, 44(10): 2983-2994.
[8]	Antai SUN, Ye LIU, Dongmei XU. Dynamic surface asymptotic compensation algorithm for multi-agent systems [J]. Journal of Computer Applications, 2024, 44(10): 3151-3157.
[9]	Chaoying YAN, Ziyi ZHANG, Yingnan QU, Qiuyu LI, Dixiang ZHENG, Lijun SUN. Double auction carbon trading based on consortium blockchain [J]. Journal of Computer Applications, 2024, 44(10): 3240-3245.
[10]	. Dung beetle optimizer algorithm with restricted reverse learning and Cauchy-Gauss variation [J]. Journal of Computer Applications, 0, (): 0-0.
[11]	Guanglei YAO, Juxia XIONG, Guowu YANG. Flower pollination algorithm based on neural network optimization [J]. Journal of Computer Applications, 2024, 44(9): 2829-2837.
[12]	Shanglong LI, Jianhua LIU, Heming JIA. Reptile search algorithm based on multi-hunting coordination strategy [J]. Journal of Computer Applications, 2024, 44(9): 2818-2828.
[13]	Yan LI, Dazhi PAN, Siqing ZHENG. Improved adaptive large neighborhood search algorithm for multi-depot vehicle routing problem with time window [J]. Journal of Computer Applications, 2024, 44(6): 1897-1904.
[14]	. Robust shapeles representation method for time series [J]. Journal of Computer Applications, 0, (): 0-0.
[15]	HU Linbo , NI Zhiwei , CHENG Jiale, LIU Wentao , ZHU Xuhui , . Complex collaborative crowdsourcing task allocation method based on fusion community detection [J]. Journal of Computer Applications, 0, (): 0-0.

Improved algorithm for vital arc of maximum dynamic flow

最大动态流关键弧的改进算法

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics