Push–relabel maximum flow algorithm: Difference between revisions

Revision as of 01:47, 11 April 2014

Revision as of 06:23, 11 April 2014

Line 6:

==Concepts==

===Definitions and notations===

{{main|Flow network}}

Line 37 ⟶ 38:

===Operations===

====Push====

The push operation applies on an admissible out-edge {{nowrap|(''u'', ''v'')}} an active vertex ''u'' in {{nowrap|''G_f''}}. It moves {{nowrap|min{''e''(''u''), ''c_f''(''u'', ''v'')}}} units of flow from ''u'' to ''v''.

Line 65 ⟶ 67:

==The generic push-relabel algorithm==

===Description===

Since {{nowrap|''h''(''s'') {{=}} {{!}}''V''{{!}}}}, {{nowrap|''h''(''t'') {{=}} 0}}, and there is not path longer than {{nowrap|({{!}}''V''{{!}} − 1)}} in {{nowrap|''G_f''}}, in order for {{nowrap|''h''(''s'')}} to satisfy the valid labeling condition, ''s'' must be disconnected from ''t''. At initialization, the algorithm fulfills this requirement by creating a preflow ''f'' that saturates all out-edges of ''s'', after which {{nowrap|''h''(''u'') {{=}} 0}} is trivially valid for all {{nowrap|''v'' ∈ ''V'' \ {''s'', ''t''}}}.

Line 327 ⟶ 330:

{{reflist|2|refs=

<ref name="clrs26">{{cite isbn/978026203293|chapter=§26 Maximum flow|pages=643–698}}</ref>

</ref>

<ref name="goldberg86">{{cite doi|10.1145/12130.12144}}</ref>

<ref name="cheriyan88">{{cite doi|10.1007/3-540-50517-2_69}}</ref>