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-01 Published:2014-04-29
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]	Fan PING, Xiaochun TANG, Yanyu PAN, Zhanhuai LI. Scheduling strategy of irregular tasks on graphics processing unit cluster [J]. Journal of Computer Applications, 2021, 41(11): 3295-3301.
[2]	Ying LEI, Wanbo ZHENG, Wei WEI, Yunni XIA, Xiaobo LI, Chengwu LIU, Hong XIE. Task offloading method based on probabilistic performance awareness and evolutionary game strategy in “cloud + edge” hybrid environment [J]. Journal of Computer Applications, 2021, 41(11): 3302-3308.
[3]	Gangzhu QIAO, Rui WANG, Chaoli SUN. Improved high-dimensional many-objective evolutionary algorithm based on decomposition [J]. Journal of Computer Applications, 2021, 41(11): 3097-3103.
[4]	Fumin ZOU, Sijie LUO, Zhihui CHEN, Lyuchao LIAO. Time-space distribution identification method of taxi shift based on trajectory data [J]. Journal of Computer Applications, 2021, 41(11): 3376-3384.
[5]	. Hybrid adaptive large neighborhood search algorithm for solving time-dependent vehicle routing problem in cold chain logistics [J]. Journal of Computer Applications, 0, (): 0-0.
[6]	. Alternately optimizing algorithm based on Brownian movement and gradient information [J]. Journal of Computer Applications, 0, (): 0-0.
[7]	. Fault diagnosis method based on improved one-dimensional convolution and bidirectional long short-term memory neural network [J]. Journal of Computer Applications, 0, (): 0-0.
[8]	. Yin-Yang-pair algorithm based on dynamic D-way splitting strategy and chaos perturbation [J]. Journal of Computer Applications, 0, (): 0-0.
[9]	. Harris hawks optimization algorithm based on chemotaxis correction [J]. Journal of Computer Applications, 0, (): 0-0.
[10]	. Influence maximization algorithm based on node coverage and structural holes [J]. Journal of Computer Applications, 0, (): 0-0.
[11]	TANG Andi, HAN Tong, XU Dengwu, XIE lei. Chaotic elite Harris hawks optimization algorithm [J]. Journal of Computer Applications, 2021, 41(8): 2265-2272.
[12]	LI Mengmeng, QIN Wei, LIU Yi, DIAO Xingchun. Hybrid ant colony optimization algorithm with brain storm optimization [J]. Journal of Computer Applications, 2021, 41(8): 2412-2417.
[13]	ZHANG Wenqiang, XING Zheng, YANG Weidong. Hybrid particle swarm optimization with multi-region sampling strategy to solve multi-objective flexible job-shop scheduling problem [J]. Journal of Computer Applications, 2021, 41(8): 2249-2257.
[14]	ZHANG Xiangfei, LU Yuming, ZHANG Pingsheng. Constrained multi-objective optimization algorithm based on coevolution [J]. Journal of Computer Applications, 2021, 41(7): 2012-2018.
[15]	ZHANG Meng, LI Weihua. Influence maximization algorithm based on user interactive representation [J]. Journal of Computer Applications, 2021, 41(7): 1964-1969.

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