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)
References in periodicals archive ?
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.
An approximate max-flow min-cut theorem for uniform multicommodity flow problems with applications to approximation algorithms.
The result (which is existentially optimal) establishes an important analogue of the famous 1-commodity max-flow min-cut theorem for problems with multiple commodities.
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?
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.