Preflow-push with excess scaling

Abstract view

Algorithmic problem: max-flow problem (standard version)

Type of algorithm: loop.

Invariant: Before and after each iteration:

1. The current flow is feasible.
2. There is a nonnegative, integral value [math]\displaystyle{ \Delta }[/math].
3. The excess of no node exceeds [math]\displaystyle{ \Delta }[/math].

Variant: [math]\displaystyle{ \Delta }[/math] is divided by two (integral division).

Break condition: [math]\displaystyle{ \Delta=0 }[/math].

Induction basis

1. All steps in the induction basis of the preflow push algorithm.
2. Set [math]\displaystyle{ \Delta:=2^L }[/math], where [math]\displaystyle{ L:=\lt math\gt \lceil\log_2U\rceil }[/math] and [math]\displaystyle{ U:=\max\{u(a)|a\in A\} }[/math].