Preflow-push: Difference between revisions

Revision as of 17:02, 26 October 2014

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 its 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

@@ Line 9: / Line 9: @@
 '''Definition:'''
 # For <math>a\in A</math>, let <math>f(a)</math> be a real number (not necessarily foring a flow). For <math>v\in V\setminus\{s,t\}</math>, the '''excess''' of <math>v</math> with respect to <math>f</math> is defined by <math>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>v\in V\setminus\{s,t\}</math> is called '''active''' it is excess is positive.
+# A node <math>v\in V\setminus\{s,t\}</math> is called '''active''' it its excess is positive.
 # Let <math>\Delta</math> denote the sum of the distance labels <math>d(v)</math> of all active nodes <math>v\in V\setminus\{s,t\}</math>.