Flow augmenting path

From Glossary

Jump to: navigation, search

This arises in the Ford-Fulkerson labeling algorithm to find a maximum flow in a network with arc flow bounds, LaTeX: L and LaTeX: U. Given a flow, LaTeX: f, from a source to a sink, a flow augmenting path, relative to LaTeX: f, is a path from that source to the sink such that

LaTeX: f(x, y) \lt U(x, y)

along all forward arcs, and

LaTeX: f(x, y) \ge L(x, y)

along all backward arcs.

The flow, LaTeX: f<, is a maximum flow from the source to the sink if and only if there is no flow augmenting path relative to LaTeX: f. If there is a flow augmenting path, it can be changed along the path such that total flow increases (by at least 1 if all data are integer).

Personal tools