Hilfe Wegweiser Datenschutzhinweis Impressum Kontakt





Multicommodity Flows Over Time: Efficient Algorithms and Complexity


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

Externe Ressourcen
Es sind keine Externen Ressourcen verfügbar
Volltexte (frei zugänglich)
Es sind keine frei zugänglichen Volltexte verfügbar
Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar

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.

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.