Multicommodity flows over time: Efficient algorithms and complexity

DOI10.1016/j.tcs.2007.02.046zbMath1149.90032OpenAlexW2012470298MaRDI QIDQ2373727

Martin Skutella, Steffen Hippler, Alex Hall

Publication date: 16 July 2007

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2007.02.046

zbMATH Keywords

complexitynetwork flowroutingefficient algorithmflow over timedynamic flow

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Communication networks in operations research (90B18)

Related Items (23)

Exact and approximate approaches for the Pareto front generation of the single path multicommodity flow problem ⋮ Minimum cost multicommodity network flow problem in time-varying networks: by decomposition principle ⋮ The impact of local policies on the quality of packet routing in paths, trees, and rings ⋮ Dynamic multicommodity contraflow problem with asymmetric transit times ⋮ A matheuristic approach for the quickest multicommodity \(k\)-splittable flow problem ⋮ Cascading knapsack inequalities: reformulation of a crude oil distribution problem ⋮ An exact algorithm for the service network design problem with hub capacity constraints ⋮ Scalable timing-aware network design via Lagrangian decomposition ⋮ The Maximum Energy-Constrained Dynamic Flow Problem ⋮ An Introduction to Network Flows over Time ⋮ Unnamed Item ⋮ Computational complexity of convoy movement planning problems ⋮ An exact algorithm for a multicommodity min-cost flow over time problem ⋮ Abstract flows over time: a first step towards solving dynamic packing problems ⋮ An efficient algorithm for the evacuation problem in a certain class of networks with uniform path-lengths ⋮ A tight bound on the speed-up through storage for quickest multi-commodity flows ⋮ A branch and price algorithm to solve the quickest multicommodity \(k\)-splittable flow problem ⋮ The universally quickest transshipment problem in a certain class of dynamic networks with uniform path-lengths ⋮ Earliest arrival flows on series-parallel graphs ⋮ Traffic Networks and Flows over Time ⋮ Heterogeneous multi-commodity network flows over time ⋮ Bounding Residence Times for Atomic Dynamic Routings ⋮ Non-approximability and Polylogarithmic Approximations of the Single-Sink Unsplittable and Confluent Dynamic Flow Problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A survey of dynamic network flows
• Transient flows in networks
• Scheduling in synchronous networks and the greedy algorithm
• Efficient continuous-time dynamic network flow algorithms
• The Quickest Transshipment Problem
• Combinatorial Optimization with Rational Objective Functions
• The quickest flow problem
• Minimum-cost dynamic flows: The series-parallel case
• A Fast Parametric Maximum Flow Algorithm and Applications
• Constructing Maximal Dynamic Flows from Static Flows
• Quickest Flows Over Time

This page was built for publication: Multicommodity flows over time: Efficient algorithms and complexity