Abstract
We provide a comprehensive study on network flow problems with arc reversal capabilities. The problem is to identify the arcs to be reversed in order to achieve a maximum flow from source(s) to sink(s). The problem finds its applications in emergency transportation management, where the lanes of a road network could be reversed to enable flow in the opposite direction. We study several network flow problems with the arc reversal capability and discuss their complexity. More specifically, we discuss the polynomial time algorithms for the maximum dynamic flow problem with arc reversal capability having a single source and a single sink, and for the maximum (static) flow problem. The presented algorithms are based on graph transformations and reductions to polynomially solvable flow problems. In addition, we show that the quickest transshipment problem with arc reversal capability and the problem of minimizing the total cost resulting from arc switching costs are \(\mathcal{NP}\) -hard.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Ahuja RK, Magnati TL, Orlin JB (1993) Network flows: theory, algorithms, and applications. Prentice Hall, Englewood Cliffs
Bern MW, Lawler EL, Wong AL (1987) Linear-time computation of optimal subgraph of decomposable graphs. J Algorithms 8:216–235
Burkard R, Dlaska K, Klinz B (1993) The quickest flow problem. Math Methods Oper Res 37(1):31–58
Cheriyan J, Maheshwari SN (1989) Analysis of preflow push algorithm for maximum network flow. SIAM J Comput 18:1057–1086
Ford FR, Fulkerson DR (1962) Flows in networks. Princeton University Press, Princeton
Garey MR, Johnson DS (1979) Computers and intractability—a guide to the theory of NP-completeness. Freeman, New York
Goldberg AV, Tarjan RE (1989) Finding minimum-cost circulations by cancelling negative cycles. J ACM 36:873–886
Gross JL, Yellen J (2003) Handbook of graph theory. Discrete mathematics and its applications. CRC, New York
Guisewite GM, Pardalos PM (1990) Minimum concave-cost network flow problems: applications, complexity, and algorithms. Ann Oper Res 25:75–100
Hajek B, Ogier RG (1984) Optimal dynamic routing in communication networks with continuous traffic. Networks 14:457–487
Hamza-Lup GL, Hua K, Lee M, Peng R (2004) Enhancing intelligent transportation systems to improve and support homeland security. In: Proceedings of the 7th international IEEE conference on intelligent transportation systems, pp 250–255
Hoppe BE (1995) Efficient dynamic network flow algorithms. PhD thesis, Cornell University. http://www.math.tu-berlin.de/~skutella/hoppe_thesis.ps.gz
Kim D, Pardalos PM (2000) Dynamic slope scaling and trust interval techniques for solving concave piecewise linear network flow problems. Networks 35(3):216–222
Kim S, Shekhar S (2005) Contraflow network reconfiguration for evaluation planning: a summary of results. In: Proceedings of the 13th annual ACM international workshop on geographic information systems, pp 250–259
Krumke S, Noltemeier H, Schwarz S, Wirth H, Ravi R (1998) Flow improvement and network flows with, fixed costs. In: Proceedings of the international conference of operations research (0R’98), Zürich, pp 158–167
Megiddo N (1979) Combinatorial optimization with rational objective functions. Math Oper Res 4:414–424
Melkonian V (2007) Flows in dynamic networks with aggregate arc capacities. Inf Process Lett 101(1):30–35
Orlin JB (1983) Maximum-throughput dynamic network flows. Math Program 27:214–231
Theodoulou G, Wolshon B (2004) Alternative methods to increase the effectiveness of freeway contraflow evacuation. J Transp Res Board 1865:48–56
Tuydes H, Ziliaskopoulos A (2006) Tabu-based heuristic approach for optimization of network evacuation contraflow. Transp Res Record 1964:157–168
Williams B, Tagliaferri A, Meinhold S, Hummer J, Rouphail N (2007) Simulation and analysis of freeway lane reversal for coastal hurricane evacuation. J Urban Plng Devel 133(1):61–72
Author information
Authors and Affiliations
Corresponding author
Additional information
This research work was funded by UF Center for Multimodal solutions for Congestion Mitigation (CMS).
Rights and permissions
About this article
Cite this article
Rebennack, S., Arulselvan, A., Elefteriadou, L. et al. Complexity analysis for maximum flow problems with arc reversals. J Comb Optim 19, 200–216 (2010). https://doi.org/10.1007/s10878-008-9175-8
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10878-008-9175-8