Blocking flow by Dinic
Revision as of 03:51, 20 October 2014 by Weihe (talk | contribs) (Created page with "== General information == '''Algorithmic problem:''' Blocking flow. '''Type of algorithm:''' loop. == Abstract view == '''Invariant:''' The current flow is feasible....")
General information
Algorithmic problem: Blocking flow.
Type of algorithm: loop.
Abstract view
Invariant: The current flow is feasible.
'Variant: The number of saturated arcs increases.
Break condition: There is no more flow-augmenting ordinary [math]\displaystyle{ (s,t) }[/math]-path in [math]\displaystyle{ G }[/math] (that is, all arcs on the path are forward arcs).