Dynamic flows with time-dependent capacities
From MaRDI portal
Abstract: Dynamic network flows, sometimes called flows over time, extend the notion of network flows to include a transit time for each edge. While Ford and Fulkerson showed that certain dynamic flow problems can be solved via a reduction to static flows, many advanced models considering congestion and time-dependent networks result in NP-hard problems. To increase understanding of these advanced dynamic flow settings we study the structural and computational complexity of the canonical extensions that have time-dependent capacities or time-dependent transit times. If the considered time interval is finite, we show that already a single edge changing capacity or transit time once makes the dynamic flow problem weakly NP-hard. In case of infinite considered time, one change in transit time or two changes in capacity make the problem weakly NP-hard. For just one capacity change, we conjecture that the problem can be solved in polynomial time. Additionally, we show the structural property that dynamic cuts and flows can become exponentially complex in the above settings where the problem is NP-hard. We further show that, despite the duality between cuts and flows, their complexities can be exponentially far apart.
Cites work
- A generalized dynamic flows problem
- An introduction to network flows over time
- Constructing maximal dynamic flows from static flows
- Continuous and discrete flows over time
- Continuous-Time Flows in Networks
- Flows over Time with Load-Dependent Transit Times
- scientific article; zbMATH DE number 1488014 (Why is no real title available?)
Cited in
(3)
This page was built for publication: Dynamic flows with time-dependent capacities
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6057324)
