HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation

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 :
Complete list of metadata

Cited literature [42 references]  Display  Hide  Download

Contributor : Rapport de Recherche Inria Connect in order to contact the contributor
Submitted on : Tuesday, May 23, 2006 - 6:23:09 PM
Last modification on : Friday, February 4, 2022 - 3:08:46 AM
Long-term archiving on: : Sunday, April 4, 2010 - 10:30:50 PM


  • HAL Id : inria-00071643, version 1



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



Record views


Files downloads