Forty-eight years after the first appearance of Ford and Fulkerson’s landmark Flows in Networks, Princeton University Press has decided to reissue the monograph. While many older texts do not stand up to the test of time, some do; count Ford and Fulkerson’s work in the latter category. It still stands up as the definitive work in the field.
This monograph represents a study of the intersection of Graph Theory, Combinatorics, and Operations Research. Proofs, for the most part, are constructive, and the network models are general enough to have relevance even today. Interestingly, the terminology “transportation problems” seems to have superseded the language of “network flows”; Ford and Fulkerson seem to have wanted to keep the ideas as general as possible for wider application. There are four chapters, and no exercises, but numerous references (albeit 50+ years old).
In the first chapter, “Static Maximal Flow,” the basics of Graph Theory and Networks are laid out. The famous Max flow/Min cut theorem is presented at the beginning of the chapter, but towards the end, the authors point out that it is a special case of the duality theorem of linear programming. In Chapter II, “Feasibility Theorems and Combinatorial Applications,” the connections between combinatorics, linear programming and network flows are discussed. Also in this chapter, the well-known Menger’s Theorem is proven, with the Konig-Egervary Theorem for bipartite graphs presented as a lemma.
In Chapter III, “Minimal Cost Flow Problems,” directed networks are used to model real-world situations, such as the “caterer problem” and “the warehouse problem.” Also, extensive treatment is afforded the “Hitchcock problem” — minimizing flow cost given a certain number of sources for a commodity, cost of shipment and demand. The utility of this analysis still resonates. In Chapter IV, “Multiterminal Maximal Flows,” the work of Gomory and Hu in this area receives a solid treatment. Prim’s Algorithm and Kruskal’s work on shortest spanning subtrees also receives coverage.
And that is all. The book ends. For classic texts to stand up to the test of time, they need to not only maintain relevance but also be forward-thinking. According to MathSciNet, Ford and Fulkerson’s monograph has received 160 citations, and impressive number for such a specialized work. Ford and Fulkerson were very conscious of the need for efficiency in their algorithms, long before such theories were fully developed. This work indeed stands the test of time.
John T. Saccoman is Professor of Mathematics at Seton Hall University in South Orange, NJ.