max-flow min-cut theorem


Also found in: Wikipedia.

max-flow min-cut theorem

[‚maks¦flō ‚min′kət ‚thir·əm]
(industrial engineering)
In the analysis of networks, the concept that for any network with a single source and sink, the maximum feasible flow from source to sink is equal to the minimum cut value for any of the cuts of the network.
(mathematics)
McGraw-Hill Dictionary of Scientific & Technical Terms, 6E, Copyright © 2003 by The McGraw-Hill Companies, Inc.
References in periodicals archive ?
First, the biggest weighted edges are obtained by max-flow min-cut theorem [20].
When there is a single demand, the minimum of [Cap(S)/Dem(S)] equals the maximum value of f, a consequence of the max-flow min-cut theorem. In general, for more than one demand there will be a gap between the values of the minimum cut and the maximum flow.
Our primary result in this paper is all approximate max-flow min-cut theorem for uniform multicommodity flow problems.
[1995] to establish an O(log C log D) max-flow min-cut theorem for arbitrary multicommodity flow problems in undirected networks, where C denotes the total capacity of the network and D denotes the total demand of the commodities.
[1996] established an O(log k) max-flow min-cut theorem for arbitrary (undirected) multicommodity flow problems where the sum of the flows is maximized (as opposed to our situation in which a common fraction of each commodity's demand is maximized).
(1) Is there a max-flow min-cut theorem similar to Theorem 2 for directed multicommodity flow problems with general demands?
In this paper, we establish max-flow min-cut theorems for several important classes of multicommodity flow problems.
We also prove approximate max-flow min-cut theorems for related classes of flow problems in which the edges in the underlying graph may be directed, the flow paths may be required to be short, and/or the constraint on the uniformity of the demands is relaxed.
For a survey of all the work on max-flow min-cut theorems and their applications to approximation algorithms, we refer the reader to the excellent article by Shmoys [1996].
In this section, we prove max-flow min-cut theorems for several classes of multicommodity flow problems.