MAXIMUM FLOW PROBLEM

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.

Contents

Solutions

References

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 sink $t$, subject to certain constraints. There are many ways of solving this problem:
{| cellpadding="10px"
! Method
! Complexity
! Description
|-
| Brute-force search
| $O(2^\{V-2\}\; E)$
| Find the minimum of all cuts separating $s$ and $t$.
|-
| Linear programming
|
| Constraints given by the definition of a legal flow. Optimize $sum\_\{v\; in\; V\}\; f(s,v)$.
|-
| Ford-Fulkerson algorithm
| $O(E\; cdot\; mathit\{maxflow\})$
| As long as there is an open path through the network, send more flow along such a path.
|-
| Edmonds-Karp algorithm
| $O(V\; E^2)$
| A specialisation of Ford-Fulkerson, finding paths with breadth-first search.
|-
| Relabel-to-front algorithm
| $O(V^3)$
| 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 .

References

# Introduction to Algorithms, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein, , , MIT Press and McGraw-Hill, 2001, ISBN 0-262-53196-8
# A new approach to the maximum-flow problem, Andrew V. Goldberg and Robert E. Tarjan, , , Journal of the ACM, 1988