Minimum flow problem on network flows with time-varying bounds
作者： H. Salehi Fathabadi , S. Khodayifar , M.A. Raayatpanah
DOI: 10.1016/J.APM.2011.11.067
关键词:
摘要: Abstract In this paper, we consider the minimum flow problem on network flows in which lower arc capacities vary with time. We will show that for set {0, 1, … , T} of time points can be solved by at most n computations, combining preflow-pull algorithm and reoptimization techniques (no matter how many values T are given). Running presented is O(n2m).
elsevier.com
sci-hub.se 参考文章(12)
Warren B. Powell, Patrick Jaillet, Amedeo Odoni, Stochastic and dynamic networks and routing Handbooks in Operations Research and Management Science. ,vol. 8, pp. 141- 295 ,(1995) , 10.1016/S0927-0507(05)80107-0
Lester Randolph Ford, Flows in networks ,(1962)
James B. Orlin, Thomas L. Magnanti, Ravindra K. Ahuja, Network Flows: Theory, Algorithms, and Applications ,(1993)
Alex Hall, Steffen Hippler, Martin Skutella, Multicommodity flows over time: Efficient algorithms and complexity Theoretical Computer Science. ,vol. 379, pp. 387- 404 ,(2007) , 10.1016/J.TCS.2007.02.046
Eleonor Ciurea, Laura Ciupalâ, Sequential and parallel algorithms for minimum flows Journal of Applied Mathematics and Computing. ,vol. 15, pp. 53- 75 ,(2004) , 10.1007/BF02935746
Bruce Edward Hoppe, Efficient dynamic network flow algorithms Cornell University. ,(1995)
Bettina Klinz, Gerhard J. Woeginger, Minimum-cost dynamic flows: The series-parallel case† Networks. ,vol. 43, pp. 153- 162 ,(2004) , 10.1002/NET.10112
L. R. Ford, D. R. Fulkerson, Constructing Maximal Dynamic Flows from Static Flows Operations Research. ,vol. 6, pp. 419- 433 ,(1958) , 10.1287/OPRE.6.3.419
Hassan Salehi Fathabadi, Seyed Ahmad Hosseini, MAXIMUM FLOW PROBLEM ON DYNAMIC GENERATIVE NETWORK FLOWS WITH TIME-VARYING BOUNDS Applied Mathematical Modelling. ,vol. 34, pp. 2136- 2147 ,(2010) , 10.1016/J.APM.2009.10.026
Jay E. Aronson, A survey of dynamic network flows Annals of Operations Research. ,vol. 20, pp. 1- 66 ,(1989) , 10.1007/BF02216922