Preflow-push with excess scaling: Difference between revisions
Jump to navigation
Jump to search
(Created page with "== Abstract view == '''Algorithmic problem:''' max-flow problem (standard version) '''Type of algorithm:''' loop. '''Invariant:''' Before and after ea...") |
|||
| Line 2: | Line 2: | ||
'''Algorithmic problem:''' | '''Algorithmic problem:''' | ||
[[Max- | [[Max-Flow Problems|max-flow problem (standard version)]] | ||
'''Type of algorithm:''' | '''Type of algorithm:''' | ||
Revision as of 13:37, 29 October 2014
Abstract view
Algorithmic problem: max-flow problem (standard version)
Type of algorithm: loop.
Invariant: Before and after each iteration:
- The current flow is feasible.
- There is a nonnegative, integral value [math]\displaystyle{ \Delta }[/math].
- The excess of no node exceeds [math]\displaystyle{ \Delta }[/math].
Variant: [math]\displaystyle{ \Delta }[/math] is divided by two (integral division).
Break condition: [math]\displaystyle{ \Delta=0 }[/math].
Induction basis
- All steps in the induction basis of the preflow push algorithm.
- Set [math]\displaystyle{ \Delta }[/math]