Flows in networks. With a new foreword by Robert G. Bland and James B. Orlin. Reprint of 1962 original. (English) Zbl 1216.05047

Ford, L. R. jun.; Fulkerson, D. R.

Princeton Landmarks in Mathematics. Princeton, NJ: Princeton University Press (ISBN 978-0-691-14667-6/pbk). 208 p. (2011).

This seminal book on network flows by Lester R. Ford, Jr. and D. Ray Fulkerson is the second edition published by Princeton University Press, and is the first Princeton Landmarks in Mathematics edition, forty-eight years after the appearance of the first edition in 1962 (see the review in Zbl 0106.34802). The only difference between the two editions is the inclusion of a new foreword by Robert G. Bland of Cornell University and James B. Orlin of Massachusetts Institute of Technology. This new foreword gives valuable historical insight on various topics covered by the book. For example, Ford and Fulkerson’s efficient computational work is three years prior to the formalization of the concept of polynomial-time algorithms and eight years prior to the development of the theory of NP-completeness. Bland and Orlin also noted that in RAND Research Memorandum RM-1400, dated 11/19/1954, Ford and Fulkerson proved the max-flow min-cut theorem, gave a maximum s-t flow algorithm for s,t-planar networks, and discussed the application to rail network capacity. Hence, the “spring 1955” date on page 1 of this book for T. E. Harris and F. S. Ross posing the maximum flow problem to them must be incorrect.
The book contains four chapters. Chapter 1 addresses the maximum flow problem and some natural variations on it. Chapter 2 deals with feasibility theorems and combinatorial applications. Chapter 3 focuses on computing minimum cost flows in directed networks with linear costs on the arcs. Finally, Chapter 4 treats multi-terminal maximal flows and some network design problems, and is mostly based on the work of Ralph Gomory and T. C. Hu.
This classic work contains a wealth of mathematical and computational results with diverse and important applications. It is indispensable for those who wish to understand the origin of this work and to benefit from it. The book is written in a concise manner with perception and is very well presented.

Reviewer: Wai-Kai Chen (Fremont)

MSC:

05C20	Directed graphs (digraphs), tournaments
05C21	Flows in graphs
05-02	Research exposition (monographs, survey articles) pertaining to combinatorics

Keywords:

maximal flow; minimum cut; directed network; multi-terminal flows

Citations:

Zbl 0139.13701; Zbl 0106.34802