Help Privacy Policy Disclaimer
  Advanced SearchBrowse




Conference Paper

Multicommodity Flows Over Time: Efficient Algorithms and Complexity


Skutella,  Martin
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource
No external resources are shared
Fulltext (restricted access)
There are currently no full texts shared for your IP range.
Fulltext (public)
There are no public fulltexts stored in PuRe
Supplementary Material (public)
There is no public supplementary material available

Hall, A., Hippler, S., & Skutella, M. (2003). Multicommodity Flows Over Time: Efficient Algorithms and Complexity. In Automata, languages and programming: 30th International Colloquium, ICALP 2003 (pp. 397-409). Berlin, Germany: Springer.

Cite as: https://hdl.handle.net/11858/00-001M-0000-000F-2D7A-7
Flow variation over time is an important feature in network flow problems arising in various applications such as road or air traffic control, production systems, communication networks (e.g., the Internet), and financial flows. The common characteristic are networks with capacities and transit times on the arcs which specify the amount of time it takes for flow to travel through a particular arc. Moreover, in contrast to static flow problems, flow values on arcs may change with time in these networks. While the `maximum $s$-$t$-flow over time' problem can be solved efficiently and `min-cost flows over time' are known to be NP-hard, the complexity of (fractional) `multicommodity flows over time' has been open for many years. We prove that this problem is NP-hard, even for series-parallel networks, and present new and efficient algorithms under certain assumptions on the transit times or on the network topology. As a result, we can draw a complete picture of the complexity landscape for flow over time problems.