Maximum flow problem

From Free net encyclopedia

(Redirected from Max flow)

The maximum flow problem is finding a legal flow through a flow network that is maximal. 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. It is the multi-commodity flow problem with only one commodity, and it is the minimum-cost flow problem with all costs set to zero. The maximal flow is related to the cuts in a network by the Max-flow min-cut theorem.

[edit]

Solutions

Given a graph <math>G(V,E)</math>, where each edge <math>u,v</math> has a capacity <math>c(u,v)</math>, we want to find a maximal flow <math>f</math> from the source <math>s</math> to the drain <math>t</math>, subject to certain constraints. There are many ways of solving this problem:

Method	Complexity	Description
Brute-force search	<math>O(2^{V-2} E)</math>	Find the minimum of all cuts separating <math>s</math> and <math>t</math>.
Linear programming		Constraints given by the definition of a legal flow. Optimize <math>\sum_{v \in V} f(s,v)</math>.
Ford-Fulkerson algorithm	<math>O(E \cdot maxflow)</math>	As long as there is an open path through the network, send more flow along such a path.
Edmonds-Karp algorithm	<math>O(V E^2)</math>	A specialisation of Ford-Fulkerson, finding paths with breadth-first search.
Relabel-to-front algorithm	<math>O(V^3)</math>	Arrange the nodes into various heights such that maximum amount of flow runs from <math>s</math> to <math>t</math> "by itself".