Network flows. Theory, algorithms, and applications. (English) Zbl 1201.90001

Ahuja, Ravindra K.; Magnanti, Thomas L.; Orlin, James B.

Englewood Cliffs, NJ: Prentice Hall (ISBN 0-13–617549-X). xvi, 846 p. (1993).

Among all topics covered in operations research, network flows theory offers the best context to illustrate the basic concepts of optimization. This book provides an integrative view of the theory, algorithms and applications of network flows. In order for their presentation to be more intuitive and accessible to a wider audience, the authors prefer to adopt a network or graphical viewpoint rather than relying on a linear programming approach. The material in this book can be used to serve the purpose of supplementing either an upper level undergraduate or graduate course.
The main features of the book are well outlined in the authors’ preface as follows: “In-depth and self-contained treatment of shortest path, maximum flow, and minimum cost flow problems, including descriptions of new and novel polynomial-time algorithms for these core models. Emphasis on powerful algorithmic strategies and analysis tools, such as data scaling, geometric improvement arguments, and potential function arguments. An easy-to-understand description of several important data structures, including \(d\)-heaps, Fibonacci heaps, and dynamic trees. Treatment of other important topics in network optimization and of practical solution techniques such as Lagrangian relaxation. Each new topic introduced by a set of applications and an entire chapter devoted to applications. A special chapter devoted to conducting empirical testing of algorithms. Over 150 applications of network flows to a variety of engineering, management, and scientific domains. Over 800 exercises that vary in difficulty, including many that develop extensions of material covered in the text. Approximately 400 figures that illustrate the material presented in the text. Extensive reference notes that provide readers with historical contexts and with guides to the literature.”
In addition to the in-depth analysis of shortest path, maximum flow, minimum cost flow problems, the authors devote several other chapters to more advanced topics such as assignments and matchings, minimum spanning trees, convex cost flows, generalized flows and multicommodity flows. Furthermore, emphasis is put on design, analysis and computation testing of algorithms.
Finally, pseudocodes for several algorithms are provided for readers with a basic knowledge of computer science.

Reviewer: Jacques A. Ferland (MR1205775)

MSC:

90-01	Introductory exposition (textbooks, tutorial papers, etc.) pertaining to operations research and mathematical programming
90B10	Deterministic network models in operations research
90C35	Programming involving graphs or networks
90-02	Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming

Software:

GIDEN