Property 22.13 The worst-case running time of the FIFO queue implementation of the preflow-push algorithm is proportional to V2E.Image

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 ...

Get Algorithms in C, Part 5: Graph Algorithms, Third Edition now with the O’Reilly learning platform.

O’Reilly members experience live online training, plus books, videos, and digital content from nearly 200 publishers.