**Property 22.13** *The worst-case running time of the FIFO queue implementation of the preflow-push algorithm is proportional to V*^{2}*E.*

*Proof*: We bound the number of phases using a *potential function*. This argument is a simple example of a powerful technique in the analysis of algorithms and data structures that we examine in more detail in Part 8.

Define the quantity φ to be 0 if there are no active vertices and to be the maximum height of the active vertices otherwise, then consider the effect of each phase on the value of φ. Let *h*0 (*s*) be the initial height of the source. At the beginning, φ =*h*0 (*s*); at the end, φ = 0.

First, we note that the number ...

Start Free Trial

No credit card required