Complexity analysis for maximum flow problems with arc reversals

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

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

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

Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, A Bicriteria Approach for Saving a Path Maximizing Dynamic Contraflow, Degree-constrained orientations of embedded graphs, Multi-commodity flow problem on lossy network with partial lane reversals, Pattern-based evacuation planning for urban areas, Generation of networks with prescribed degree-dependent clustering, Efficient contraflow algorithms for quickest evacuation planning, Continuous time dynamic contraflow models and algorithms, Evacuation network optimization model with Lane-based reversal and routing, Network design model to integrate shelter assignment with contraflow operations in emergency evacuation planning, Abstract network flow with intermediate storage for evacuation planning, Dynamic multicommodity contraflow problem with asymmetric transit times, Network flow with intermediate storage: models and algorithms, Partial contraflow with path reversals for evacuation planning, Evacuation planning by earliest arrival contraflow, Continuous dynamic contraflow approach for evacuation planning, Efficient continuous contraflow algorithms for evacuation planning problems, A survey on models and algorithms for discrete evacuation planning network problems, Dynamic network flow location models and algorithms for quickest evacuation planning

Cites Work

• 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
• Dynamic slope scaling and trust interval techniques for solving concave piecewise linear network flow problems
• Linear-time computation of optimal subgraphs of decomposable graphs