Skip to Main content Skip to Navigation
Reports

An annotated overview of dynamic network flows

Balázs Kotnyek 1
1 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : The need for more realistic network models led to the development of the dynamic network flow theory. In dynamic flow models it takes time for the flow to pass an arc, the flow can be delayed at nodes, and the network parameters, e.g., the arc capacities, can change in time. Surprisingly perhaps, despite being closer to reality, dynamic flow models have been overshadowed by the classical, static model. This is largely due to the fact that while very efficient solution methods exist for static flow problems, dynamic flow problems have proved to be more difficult to solve. Our purpose with this overview is to compensate for this eclipse and introduce dynamic flows to the interested reader. To this end, we present the main flow problems that can appear in a dynamic network, and review the literature for existing results about them. Our approach is solution oriented, as opposed to dealing with modelling issues. We intend to provide a survey that can be a first step for readers wondering whether a given dynamic network flow problem has been solved or not. Besides restating the problems, we also describe the main proposed solution methods. An additional feature of this paper is an annotated list of the most important references about the subject.
Document type :
Reports
Complete list of metadata

Cited literature [42 references]  Display  Hide  Download

https://hal.inria.fr/inria-00071643
Contributor : Rapport de Recherche Inria <>
Submitted on : Tuesday, May 23, 2006 - 6:23:09 PM
Last modification on : Wednesday, October 14, 2020 - 4:23:57 AM
Long-term archiving on: : Sunday, April 4, 2010 - 10:30:50 PM

Identifiers

  • HAL Id : inria-00071643, version 1

Collections

Citation

Balázs Kotnyek. An annotated overview of dynamic network flows. RR-4936, INRIA. 2003. ⟨inria-00071643⟩

Share

Metrics

Record views

525

Files downloads

4627