Preflow-push: Difference between revisions
Jump to navigation
Jump to search
(Created page with "== Abstract view == '''Algorithmic problem:''' max-flow probem (standard version) '''Type of algorithm:''' loop. '''Definition:''' # For <math>a\in A</...") |
No edit summary |
||
Line 2: | Line 2: | ||
'''Algorithmic problem:''' | '''Algorithmic problem:''' | ||
[[Max-flow | [[Max-flow problems|max-flow problem (standard version)]] | ||
'''Type of algorithm:''' | '''Type of algorithm:''' |
Revision as of 17:00, 26 October 2014
Abstract view
Algorithmic problem: max-flow problem (standard version)
Type of algorithm: loop.
Definition:
- For [math]\displaystyle{ a\in A }[/math], let [math]\displaystyle{ f(a) }[/math] be a real number (not necessarily foring a flow). For [math]\displaystyle{ v\in V\setminus\{s,t\} }[/math], the excess of [math]\displaystyle{ v }[/math] with respect to [math]\displaystyle{ f }[/math] is defined by
- [math]\displaystyle{ e_f(v):=\sum_{w:(w,v)\in A}f(w,v)-\sum_{w:(v,w)\in A}f(v,w) }[/math].
- A node [math]\displaystyle{ v\in V\setminus\{s,t\} }[/math] is called active it is excess is positive.
- Let [math]\displaystyle{ \Delta }[/math] denote the sum of the distance labels [math]\displaystyle{ d(v) }[/math] of all active nodes [math]\displaystyle{ v\in V\setminus\{s,t\} }[/math].
Invariant: Before and after each iteration:
- For each arc [math]\displaystyle{ a\in A }[/math], it is [math]\displaystyle{ 0\leq f(a)\leq u(a) }[/math] .
- For each node [math]\displaystyle{ v\in V }[/math], it is [math]\displaystyle{ e_f(v)\geq 0 }[/math].
- The node labels [math]\displaystyle{ d }[/math] form a valid distance labeling, and it is [math]\displaystyle{ d(s)=|V| }[/math].
Variant: At least one
- The label of at least one node increases.
- The push is saturating.
- The value of [math]\displaystyle{ \Delta }[/math] decreases.
Induction basis
- Set