Complexity analysis for maximum flow problems with arc reversals

DOI10.1007/s10878-008-9175-8zbMath1184.90025MaRDI QIDQ965819

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

Publication date: 26 April 2010

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-008-9175-8

zbMATH Keywords

complexity analysis; contraflow problem; dynamic contraflow problem

Mathematics Subject Classification ID

90C60: Abstract computational complexity for mathematical programming problems

90B10: Deterministic network models in operations research

Related Items

Degree-constrained orientations of embedded graphs, Pattern-based evacuation planning for urban areas, Generation of networks with prescribed degree-dependent clustering, A survey on models and algorithms for discrete evacuation planning network problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Flows in dynamic networks with aggregate arc capacities
• Minimum concave-cost network flow problems: Applications, complexity, and algorithms
• Analysis of Preflow Push Algorithms for Maximum Network Flow
• Optimal dynamic routing in communication networks with continuous traffic
• Finding minimum-cost circulations by canceling negative cycles
• Maximum-throughput dynamic network flows
• Combinatorial Optimization with Rational Objective Functions
• The quickest flow problem
• Linear-time computation of optimal subgraphs of decomposable graphs