Dinic
Revision as of 13:00, 13 October 2014 by Weihe (talk | contribs) (Created page with "== General Information == '''Algorithmic problem:''' Max-Flow Problems '''Type of algorithm :''' loop. == Abstract View == '''Invariant:''' After <math>i \ge 0</math>...")
General Information
Algorithmic problem: Max-Flow Problems
Type of algorithm : loop.
Abstract View
Invariant: After [math]\displaystyle{ i \ge 0 }[/math] iterations: The flow [math]\displaystyle{ f }[/math] is feasible. If all upper bounds are integral, the [math]\displaystyle{ f }[/math]-values are integral as well.
Variant: The smallest number of arcs n a flow-augmenting [math]\displaystyle{ (s,t) }[/math]-path strictly increases.