Handbook of Graph Theory, 2nd Edition

Chapter 11

Networks and Flows

Section 11.1 Maximum Flows

Clifford Stein

Columbia University

Introduction

The Maximum Flow Problem is one of the basic problems in combinatorial optimization. It models a large variety of problems in a diverse set of application areas including data flowing through a communications network, power flowing through an electrical network, liquids flowing through pipes and parts flowing through a factory. It has also served as a prototypical problem in algorithm design, and many useful and powerful ideas were first introduced in the context of maximum flows. This section will describe maximum flows and some generalizations. The book by Ahuja, Magnanti and Orlin [AhMaOr93] is an excellent reference and includes a large ...