Multicommodity flows over time: Efficient algorithms and complexity

DOI10.1016/J.TCS.2007.02.046MaRDI QIDQ2373727zbMATH OpenOpenAlexFDO

Authors Alex Hall, Steffen Hippler, Martin Skutella

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

complexitydynamic flowefficient algorithmflow over timenetwork flowrouting

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 2038726
• An FPTAS for quickest multicommodity flows with inflow-dependent transit times
• An FPTAS for quickest multicommodity flows with inflow-dependent transit times
• Quickest Flows Over Time
• Maximum multicommodity flows over time without intermediate storage

Cites work

• A Fast Parametric Maximum Flow Algorithm and Applications
• A survey of dynamic network flows
• Combinatorial Optimization with Rational Objective Functions
• Constructing maximal dynamic flows from static flows
• Efficient continuous-time dynamic network flow algorithms
• scientific article; zbMATH DE number 2038726 (Why is no real title available?)
• scientific article; zbMATH DE number 2079322 (Why is no real title available?)
• scientific article; zbMATH DE number 2086912 (Why is no real title available?)
• scientific article; zbMATH DE number 3225808 (Why is no real title available?)
• scientific article; zbMATH DE number 956788 (Why is no real title available?)
• Minimum-cost dynamic flows: The series-parallel case
• Quickest Flows Over Time
• Scheduling in synchronous networks and the greedy algorithm
• The quickest flow problem
• The quickest transshipment problem
• Transient flows in networks

Cited in

(44)

• One, two, three, many, or: Complexity aspects of dynamic network flows with dedicated arcs
• Exact and approximate approaches for the Pareto front generation of the single path multicommodity flow problem
• A matheuristic approach for the quickest multicommodity \(k\)-splittable flow problem
• An exact algorithm for a multicommodity min-cost flow over time problem
• Robust flows over time: models and complexity results
• A tight bound on the speed-up through storage for quickest multi-commodity flows
• Speeding up Karmarkar's algorithm for multicommodity flows
• Heterogeneous multi-commodity network flows over time
• Dynamic multicommodity contraflow problem with asymmetric transit times
• Abstract flows over time: a first step towards solving dynamic packing problems
• A branch and price algorithm to solve the quickest multicommodity \(k\)-splittable flow problem
• Cascading knapsack inequalities: reformulation of a crude oil distribution problem
• On the complexity of instationary gas flows
• Online Multi-Commodity Flow with High Demands
• Maximum multicommodity flows over time without intermediate storage
• Graph orientation and flows over time
• An introduction to network flows over time
• Earliest arrival flows on series-parallel graphs
• The Maximum Energy-Constrained Dynamic Flow Problem
• (Almost) Tight bounds and existence theorems for single-commodity confluent flows
• The Access-Control Problem on Capacitated FIFO Networks With Unique O-D Paths is Hard
• Traffic Networks and Flows over Time
• Routing multi-class traffic flows in the plane
• scientific article; zbMATH DE number 508835 (Why is no real title available?)
• scientific article; zbMATH DE number 2038726 (Why is no real title available?)
• Computational complexity of convoy movement planning problems
• A critical survey on the network optimization algorithms for evacuation planning problems
• Non-approximability and polylogarithmic approximations of the single-sink unsplittable and confluent dynamic flow problems
• Bounding Residence Times for Atomic Dynamic Routings
• An FPTAS for quickest multicommodity flows with inflow-dependent transit times
• An exact algorithm for the service network design problem with hub capacity constraints
• Scalable timing-aware network design via Lagrangian decomposition
• One, two, three, many, or: complexity aspects of dynamic network flows with dedicated arcs
• The non-stop disjoint trajectories problem
• Integer linear programming formulations for the fleet quickest routing problem on grids
• Distributionally robust chance-constrained multicommodity network flow problem in dynamic networks: a column-generation approach
• Inflow-dependent quickest multi-commodity flow problem with partial lane reversals
• Network restructuring for dynamic flow improvement
• Network flow problems with electric vehicles
• The universally quickest transshipment problem in a certain class of dynamic networks with uniform path-lengths
• 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
• An FPTAS for quickest multicommodity flows with inflow-dependent transit times
• An efficient algorithm for the evacuation problem in a certain class of networks with uniform path-lengths

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2373727)