Algorithms in C, Part 5: Graph Algorithms, Third Edition

Property 22.13 The worst-case running time of the FIFO queue implementation of the preflow-push algorithm is proportional to V²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 h0 (s) be the initial height of the source. At the beginning, φ =h0 (s); at the end, φ = 0.

First, we note that the number ...