hide
Free keywords:
-
Abstract:
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.
