Complexity analysis for maximum flow problems with arc reversals

Steffen Rebennack, Ashwin Arulselvan, Lily Elefteriadou, Panos M. Pardalos

Research output: Contribution to journalArticle

28 Citations (Scopus)

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 NP -hard.
Original languageEnglish
Pages (from-to)200-216
Number of pages17
JournalJournal of Combinatorial Optimization
Volume19
Issue number2
DOIs
Publication statusPublished - 28 Feb 2010

Keywords

  • contraflow problem
  • dynamic contraflow problem
  • complexity analysis

Fingerprint Dive into the research topics of 'Complexity analysis for maximum flow problems with arc reversals'. Together they form a unique fingerprint.

  • Cite this