O'Reilly logo

Analysis of Complex Networks by Frank Emmert-Streib, Matthias Dehmer

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

15.1 Introduction

Dynamic flow problems are among the most important and challenging problems in network optimization due to the large size of these models in real-world applications. Dynamic flows are widely used in modelling of control processes from different technical, economic, biological and informational systems. Road traffic assignment, evacuation planning, production and distribution, schedule planning, telecommunications, modeling of biological and ecological systems, and management problems can be formulated and solved as single-commodity or multicommodity flow problems [1–3, 36].

The field of network flows blossomed in the 1940s and 1950s with interest in transportation planning and has developed rapidly since then. There is a significant body of literature devoted to this subject (see, for example, [1, 3, 11, 26, 34]). However, it has largely ignored a crucial aspect of transportation: transportation occurs over time. In the 1960s, Ford and Fulkerson [19, 20] introduced flows over time to include time in the network model and proposed scheme for the reduction of the dynamic maximum flow problem with fixed transit times and capacities of arcs to the static maximum flow problem.

The following two aspects of dynamic flows distinguish them from the traditional model. Firstly, the flow value on an arc may change over time. This feature is important in applications where supply and demand are not given as fixed measures; instead, they change over time. Naturally, the flow ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required