Maximum flow problem
From Wikipedia, the free encyclopedia
An example of a flow network with a maximum flow. The source is s, and the sink t
The maximum flow problem is to find a feasible flow through a single-source, single-sink flow network that is maximum↑ . Sometimes it is defined as finding the value of such a flow. The maximum flow problem can be seen as special case of more complex network flow problems, as the circulation problem. The maximum s-t (source-to-sink) flow in a network is equal to the minimum cardinality s-t cut in the network, as stated in the Max-flow min-cut theorem.
[edit] Solutions
Given a directed graph G(V,E), where each edge u,v has a capacity c(u,v), we want to find a maximal flow f from the source s to the drain t, subject to certain constraints. There are many ways of solving this problem:
| Method | Complexity | Description |
|---|---|---|
| Brute-force search | O(2V − 2E) | Find the minimum of all cuts separating s and t. |
| Linear programming | Constraints given by the definition of a legal flow. Optimize  . |
|
| Ford-Fulkerson algorithm |  |
As long as there is an open path through the network, send more flow along such a path. |
| Edmonds-Karp algorithm | O(VE2) | A specialisation of Ford-Fulkerson, finding paths with breadth-first search. |
| Relabel-to-front algorithm | O(V3) | Arrange the nodes into various heights such that maximum amount of flow runs from s to t "by itself". |
For a more extensive list, see ↑ .
[edit] References
- ↑ Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein (2001). "26", Introduction to Algorithms, second edition, MIT Press and McGraw-Hill, 643–700. ISBN 0-262-53196-8.
- ↑ Andrew V. Goldberg and Robert E. Tarjan (1988). "A new approach to the maximum-flow problem". Journal of the ACM 35: 921–940. DOI:10.1145/48014.61051. ISSN 0004-5411.
