Push–relabel maximum flow algorithm: Difference between revisions

Revision as of 22:46, 10 April 2014

Revision as of 23:12, 10 April 2014

Line 83:

==Practical implementations==

While the generic push-relabel algorithm has {{nowrap|''O''(''V''²''E'')}} time complexity, efficient implementations can achieve {{nowrap|''O''(''V''³)}} or lower time complexity by enforcing appropriate rules in selecting applicable push and relabel operations. The empirical performance can be further improved by heuristics.

==="Current-edge" data structure and discharge operation===

Line 118:

The algorithm has {{nowrap|''O''(''V''^2{{sqrt|''E''}})}} time complexity.

===Heuristics===

Heuristics can improve the empirical performance of the push-relabel algorithm. Commonly used heuristics include the gap heuristic and the global relabeling heuristic. The gap heuristic detects gaps in the height function. If there is height {{nowrap|0 < ''h̃'' < ''n''}} for which there is no vertex ''u'' such that {{nowrap|''h''(''u'') {{=}} ''h̃''}}, then any vertex ''u'' with {{nowrap|''h̃'' < ''h''(''u'') < ''n''}} has been disconnected from ''t'' and can be relabeled to {{nowrap|(''n'' + 1)}} immediately. The global relabeling heuristic periodically performs backward breadth-first search from ''t'' in {{nowrap|''G_f''}} to compute the exact heights of the vertices. Both heuristics skips unhelpful relabel operations, which are a bottleneck of the algorithm and contribute to the ineffectiveness of dynamic trees.<ref name="goldberg08"/>

==Sample implementations==