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 Third Edition in C now with O’Reilly online learning.

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