FIFO preflow-push
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]. 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 algorithm into phases.