FIFO preflow-push: Difference between revisions
| Line 11: | Line 11: | ||
'''Proof:''' | '''Proof:''' | ||
The complexity considerations for the [[Preflow-push|generic preflow-push algorithm]] yield <math>\mathcal{O}(n^2)</math> relabel operations and <math>\mathcal{O}(n\cdot m)</math> saturating push operations, where <math>m=|A| | The complexity considerations for the [[Preflow-push|generic preflow-push algorithm]] yield <math>\mathcal{O}(n^2)</math> relabel operations and <math>\mathcal{O}(n\cdot m)</math> saturating push operations, where <math>m=|A|</math>. There it was also shown that the total number of changes of outgoing arcs is in <math>\mathcal{O}(n^3)</math>. Hence, it rmains to show that the total number of non-saturating push operations is in <math>\mathcal{O}(n^3)</math>. | ||
Conceptually, we may partition the iterations main loop into ''phases''. The first phase commences with the very first iteration. A new phase commences as soon as all nodes that were in <math>Q</math> at the beginning fof the last phase, have been extracted once from <matH>Q</math>. Before and after each iteration, let <math>D</math> denote the maximum label <math>d(v)</math> of any active node <math>v\in V\setminus\{s,t\}</math>. In particular, it is always <math>0\leq D\leq 2n</math>. We make a case distinction: | Conceptually, we may partition the iterations main loop into ''phases''. The first phase commences with the very first iteration. A new phase commences as soon as all nodes that were in <math>Q</math> at the beginning fof the last phase, have been extracted once from <matH>Q</math>. Before and after each iteration, let <math>D</math> denote the maximum label <math>d(v)</math> of any active node <math>v\in V\setminus\{s,t\}</math>. In particular, it is always <math>0\leq D\leq 2n</math>. We make a case distinction: | ||
# In a phase in which no relabeling operations occurs, <math>D</math> is decreased by at least one because then every active node <math>v</math> leaves all of its excess to nodes <math>w</math> such that <math>d(w)=d(v)-1</math>. | # In a phase in which no relabeling operations occurs, <math>D</math> is decreased by at least one because then every active node <math>v</math> leaves all of its excess to nodes <math>w</math> such that <math>d(w)=d(v)-1</math>. | ||
Revision as of 11:37, 29 October 2014
Abstract view
This is a specialization of Preflow-push:
- The set of all active nodes is stored in a FIFO queue [math]\displaystyle{ Q }[/math].
- While the first node in [math]\displaystyle{ Q }[/math] is active and has an admissible arc, choose this node.
Complexity
Statement: The asymptotic complexity is in [math]\displaystyle{ \mathcal{O}(n^3) }[/math], where [math]\displaystyle{ n=|V| }[/math].
Proof: The complexity considerations for the generic preflow-push algorithm yield [math]\displaystyle{ \mathcal{O}(n^2) }[/math] relabel operations and [math]\displaystyle{ \mathcal{O}(n\cdot m) }[/math] saturating push operations, where [math]\displaystyle{ m=|A| }[/math]. There it was also shown that the total number of changes of outgoing arcs is in [math]\displaystyle{ \mathcal{O}(n^3) }[/math]. Hence, it rmains to show that the total number of non-saturating push operations is in [math]\displaystyle{ \mathcal{O}(n^3) }[/math].
Conceptually, we may partition the iterations main loop into phases. The first phase commences with the very first iteration. A new phase commences as soon as all nodes that were in [math]\displaystyle{ Q }[/math] at the beginning fof the last phase, have been extracted once from [math]\displaystyle{ Q }[/math]. Before and after each iteration, let [math]\displaystyle{ D }[/math] denote the maximum label [math]\displaystyle{ d(v) }[/math] of any active node [math]\displaystyle{ v\in V\setminus\{s,t\} }[/math]. In particular, it is always [math]\displaystyle{ 0\leq D\leq 2n }[/math]. We make a case distinction:
- In a phase in which no relabeling operations occurs, [math]\displaystyle{ D }[/math] is decreased by at least one because then every active node [math]\displaystyle{ v }[/math] leaves all of its excess to nodes [math]\displaystyle{ w }[/math] such that [math]\displaystyle{ d(w)=d(v)-1 }[/math].