Push–relabel maximum flow algorithm: Difference between revisions

Revision as of 09:11, 12 April 2014

Revision as of 09:12, 12 April 2014

Line 131:

The algorithm is typically separated into two phases. Phase one computes a maximum preflow by discharging only active vertices whose heights are below ''n''. Phase two converts the maximum preflow into a maximum flow by returning excess flow that cannot reach ''t'' to ''s''. It can be shown that phase two has {{nowrap|''O''(''VE'')}} time complexity regardless of the order of push and relabel operations and is therefore dominated by phase one. Alternatively, it can be implemented using flow decomposition.<ref name="amo93"/>

Heuristics are crucial to improving the empirical performance of the algorithm.<ref name="cherkassky95"/> Two commonly used heuristics are the gap heuristic and the global relabeling heuristic.<ref name="goldberg86"/><ref name="derigs89"/> The gap heuristic detects gaps in the height function. If there is a height {{nowrap|0 < ''h̃'' < {{!}}''nV''{{!}}}} for which there is no vertex ''u'' such that {{nowrap|''h''(''u'') {{=}} ''h̃''}}, then any vertex ''u'' with {{nowrap|''h̃'' < ''h''(''u'') < {{!}}''nV''{{!}}}} has been disconnected from ''t'' and can be relabeled to {{nowrap|({{!}}''nV''{{!}} + 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==