Introduction to Network Flow Problems

From IFORS Education Resources
Jump to: navigation, search

By: Hung Q. Ngo

The augmenting path method

Since the 0-flow is always feasible, one might attempt to gradually increase the flow until the flow gets its maximum value. By definition, in order to increase the flow we have to either increase f(s, v) of an out-edge (s, v) from s or decrease f(v, s) of an in-edge (v, s) to s, as long as the capacity constraint for that edge is still valid. Doing so, however, requires adjusting the flows at edges incident to v so that the flow conservation constraint at v is still valid. In fact, this kind of update shall propagate down to t, which is the place where the conservation constraint does not have to hold. The propagation, as described above, can be done via a “path” from s to t. We make this notion mathematically precise by introducing the notion of a residual network as follows.

Link to material:

Personal tools