Max flow problem

From Glossary

Jump to: navigation, search

In a network, LaTeX: [V, A], there are two special nodes in LaTeX: V: a source LaTeX: (s) and a sink LaTeX: (t). The problem is to maximize the flow from LaTeX: s to LaTeX: 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.

This can also be obtained from the duality of the following linear program:

maximize LaTeX: v:

LaTeX: 0 \le x_{ij} \le U_{ij} for LaTeX: (i, j) \in A;

LaTeX: \sum_j x_{ij} - \sum_j x_{ji} = 0 for LaTeX: i \in V \backslash \{s,t\};

LaTeX: \sum_j x_{sj} - \sum_j x_{js} = v;

LaTeX: \sum_j x_{tj} - \sum_j x_{jt} = -v.

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

Personal tools