Push–relabel maximum flow algorithm: Difference between revisions

Revision as of 04:19, 18 April 2014

Revision as of 13:35, 7 July 2014

Line 112:

====FIFO selection rule====

The [[FIFO]] push–relabel algorithm<ref name="goldberg86"/> organizes the active vertices into a queue. The initial active nodes can be inserted in arbitrary order. The algorithm always removes the vertex at the front of the queue for discharging. Whenever an inactive vertex is becomes active, it is appended to the back of the queue.

The algorithm has {{nowrap|''O''(''V''³)}} time complexity.