Blocking flow by Dinic: Difference between revisions
Jump to navigation
Jump to search
(Created page with "== General information == '''Algorithmic problem:''' Blocking flow. '''Type of algorithm:''' loop. == Abstract view == '''Invariant:''' The current flow is feasible....") |
|||
| Line 10: | Line 10: | ||
The current flow is feasible. | The current flow is feasible. | ||
'''Variant:'' | '''Variant:''' | ||
The number of saturated arcs increases. | The number of saturated arcs increases. | ||
'''Break condition:''' | '''Break condition:''' | ||
There is no more [[Basic flow definitions#Flow-augmenting path|flow-augmenting]] ordinary <math>(s,t)</math>-path in <math>G</math> (that is, all arcs on the path are forward arcs). | There is no more [[Basic flow definitions#Flow-augmenting path|flow-augmenting]] ordinary <math>(s,t)</math>-path in <math>G</math> (that is, all arcs on the path are forward arcs). | ||
Revision as of 03:51, 20 October 2014
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).