Edmonds-Karp: Difference between revisions
Jump to navigation
Jump to search
(Created page with "== General Information == '''Algorithmic problem:''' Max-Flow Problems <br> '''Type of algorithm:''' loop<br> ' == Abstract View == '''Invariant:''' After <math>i \ge...") |
|||
| Line 18: | Line 18: | ||
'''Variant:''' | '''Variant:''' | ||
# The smallest number of arcs on a flow-aumenting <math>(s,t)</math>-path increases (non-strictly) monotonously. | # The smallest number of arcs on a flow-aumenting <math>(s,t)</math>-path increases (non-strictly) monotonously. | ||
# | # Whenever that number does ''not'' decrease in an iteration, the size of <math>A_f</math> decreases. | ||
'''Break condition:''' There is no flow-augumenting path. | '''Break condition:''' There is no flow-augumenting path. | ||
Revision as of 19:45, 12 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 a fleasible flow.
- If all upper bounds are integral, [math]\displaystyle{ f }[/math] is integral as well.
Notation: For an [math]\displaystyle{ (s,t) }[/math]-flow, let [math]\displaystyle{ A_f }[/math] denote the set of all arcs that belong to at least one flow-augmenting [math]\displaystyle{ (s,t) }[/math]-path with smallest number of arcs.
Variant:
- The smallest number of arcs on a flow-aumenting [math]\displaystyle{ (s,t) }[/math]-path increases (non-strictly) monotonously.
- Whenever that number does not decrease in an iteration, the size of [math]\displaystyle{ A_f }[/math] decreases.
Break condition: There is no flow-augumenting path.