Complexity analysis for maximum flow problems with arc reversals

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

Research output: Contribution to journalArticle

25 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.
LanguageEnglish
Pages200-216
Number of pages17
JournalJournal of Combinatorial Optimization
Volume19
Issue number2
DOIs
Publication statusPublished - 28 Feb 2010

Fingerprint

Maximum Flow
Complexity Analysis
Reversal
Arc of a curve
Costs
Polynomials
Network Flow Problem
Graph Reduction
Graph Transformation
Road Network
Emergency
Polynomial-time Algorithm
NP-complete problem

Keywords

  • contraflow problem
  • dynamic contraflow problem
  • complexity analysis

Cite this

Rebennack, Steffen ; Arulselvan, Ashwin ; Elefteriadou, Lily ; Pardalos, Panos M. / Complexity analysis for maximum flow problems with arc reversals. In: Journal of Combinatorial Optimization. 2010 ; Vol. 19, No. 2. pp. 200-216.
@article{668a865b1f714c54b3ea220080c2e791,
title = "Complexity analysis for maximum flow problems with arc reversals",
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.",
keywords = "contraflow problem, dynamic contraflow problem, complexity analysis",
author = "Steffen Rebennack and Ashwin Arulselvan and Lily Elefteriadou and Pardalos, {Panos M.}",
year = "2010",
month = "2",
day = "28",
doi = "10.1007/s10878-008-9175-8",
language = "English",
volume = "19",
pages = "200--216",
journal = "Journal of Combinatorial Optimization",
issn = "1382-6905",
publisher = "Springer",
number = "2",

}

Complexity analysis for maximum flow problems with arc reversals. / Rebennack, Steffen; Arulselvan, Ashwin; Elefteriadou, Lily; Pardalos, Panos M.

In: Journal of Combinatorial Optimization, Vol. 19, No. 2, 28.02.2010, p. 200-216.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Complexity analysis for maximum flow problems with arc reversals

AU - Rebennack, Steffen

AU - Arulselvan, Ashwin

AU - Elefteriadou, Lily

AU - Pardalos, Panos M.

PY - 2010/2/28

Y1 - 2010/2/28

N2 - 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.

AB - 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.

KW - contraflow problem

KW - dynamic contraflow problem

KW - complexity analysis

UR - http://link.springer.com/journal/10878

U2 - 10.1007/s10878-008-9175-8

DO - 10.1007/s10878-008-9175-8

M3 - Article

VL - 19

SP - 200

EP - 216

JO - Journal of Combinatorial Optimization

T2 - Journal of Combinatorial Optimization

JF - Journal of Combinatorial Optimization

SN - 1382-6905

IS - 2

ER -