Dinic: Difference between revisions
Jump to navigation
Jump to search
(Created page with "== General Information == '''Algorithmic problem:''' Max-Flow Problems '''Type of algorithm :''' loop. == Abstract View == '''Invariant:''' After <math>i \ge 0</math>...") |
No edit summary |
||
| Line 13: | Line 13: | ||
'''Variant:''' | '''Variant:''' | ||
The smallest number of arcs n a flow-augmenting <math>(s,t)</math>-path strictly increases. | The smallest number of arcs n a flow-augmenting <math>(s,t)</math>-path strictly increases. | ||
== Induction basis == | |||
'''Abstract view:''' | |||
Initialize <math>f<math> as an arbitrary feasible flow, for example, the zero flow. | |||
'''Proof:''' | |||
Nothing to show. | |||
Revision as of 13:12, 13 October 2014
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.
Induction basis
Abstract view: Initialize <math>f<math> as an arbitrary feasible flow, for example, the zero flow.
Proof: Nothing to show.