About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Paper
A generalization of max flow—min cut
Abstract
We present a theorem which generalizes the max flow—min cut theorem in various ways. In the first place, all versions of m.f.—m.c. (emphasizing nodes or arcs, with graphs directed or undirected, etc.) will be proved simultaneously. Secondly, instead of merely requiring that cuts block all paths, we shall require that our general cuts be weight assignments which meet paths in amounts satisfying certain lower bounds. As a consequence, our general theorem will not only include as a special case m.f.—m.c., but also includes the existence of integral solutions to a transportation problem (with upper bounds on row and column sums) and its dual. © 1974, The Mathematical Programming Society. All rights reserved.