A Note on the Maximum Flow Through a Network [Bell Monograph]

New York, N.Y.: Bell Telephone Laboratories, Incorporated, 1957. First Separate Edition. Wraps. Near Fine. First Separate Edition. 117-119, [1-blank] pages. 10 7/8 x 8 3/8 inches (275 x 213 mm). Publisher's printed grey, blue and black wrappers. Stapled, with five holes punched at the spine as issued. Wraps. The I. R. E. Transactions on Information Theory, Vol. IT-2, pp 117-119, December 1956 first published this paper. We are not aware of an IRE offprint of this paper. Unless an IRE offprint is discovered, this Bell Telephone Systems Monograph (#2768: May 1957) constitutes the first separate edition.

"In computer science and optimization theory, the max-flow min-cut theorem states that in a flow network, the maximum amount of flow passing from the source to the sink is equal to the total weight of the edges in a minimum cut, i.e., the smallest total weight of the edges which if removed would disconnect the source from the sink....An account of the discovery of the theorem was given by Ford and Fulkerson in 1962...Determining a maximal steady state flow from one point to another in a network subject to capacity limitations on arcs ... was posed to the authors in the spring of 1955 by T.E. Harris, who, in conjunction with General F. S. Ross (Ret.) had formulated a simplified model of railway traffic flow, and pinpointed this particular problem as the central one suggested by the model. It was not long after this until the main result, Theorem 5.1, which we call the max-flow min-cut theorem, was conjectured and established. A number of proofs [ including the present paper ] have since appeared."

"This note discusses the problem of maximizing the rate of flow from one terminal to another, through a network which consists of a number of branches, each of which has a limited capacity. The main result is a theorem: The maximum possible flow from left to right through a network is equal to the minimum value among all simple cut-sets. This theorem is applied to solve a more general problem, in which a number of input nodes and a number of output nodes are used." (Summary)

PROVENANCE: The personal files of Claude E. Shannon (unmarked). There were multiple examples of this item in Shannon's files.

REFERENCES:
Sloane and Wyner, "Claude Elwood Shannon Collected Papers," #110.

COLLECTORS NOTE: The Bell Telephone System Monograph series offered a way to obtain individual articles by Bell scientists regardless of where their work was first published. Many Monographs significantly postdate the original article publication. Because of this, they rarely constitute the coveted (and traditional) article offprint. If the journal of record issued no offprint, the Monograph might be the first separate publication - the closest the collector can come to a traditional offprint. We have done our best to place each Monograph properly in the article's publishing history and welcome any corrections or additional information, especially regarding issues unknown to us.