MAX FLOW PROBLEM

Max flow problem - In a network , [V, A], there are two special nodes in V: a source (s) and a sink (t). The problem is to maximize the flow from s to t subject to conservation of flow constraints at each node and flow bounds on each arc. The max flow labeling algorithm provides a constructive proof of the Max flow - Min cut theorem . Further details are in the supplement, Ford-Fulkerson Max Flow Labeling Algorithm, as pdf   or ps .  This can also be obtained from the duality of the following linear program :

maximize v:  0 <= x(i, j) <= U(i, j) for (i, j) in A; Sum_j(x(i, j)) - Sum_j(x(j, i)) = 0   for i in V \ (s,t); Sum_j(x(s, j)) - Sum_j(x(j, s)) = v; Sum_j(x(t, j)) - Sum_j(x(j, t)) = -v.

U are upper bounds (capacities) on arc flows, and each sum is for j such that the indicated arc is in A.