FIFO preflow-push: Difference between revisions

From Algowiki
Jump to navigation Jump to search
Line 13: Line 13:
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>. Both function classes are subsets of <math>\mathcal{O}(n^3)</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>.
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>. Both function classes are subsets of <math>\mathcal{O}(n^3)</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 algorithm into ''phases''.
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>.

Revision as of 18:14, 27 October 2014

Abstract view

This is a specialization of Preflow-push:

  1. The set of all active nodes is stored in a FIFO queue [math]\displaystyle{ Q }[/math].
  2. 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]. Both function classes are subsets of [math]\displaystyle{ \mathcal{O}(n^3) }[/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].