FIFO preflow-push: Difference between revisions

From Algowiki
Jump to navigation Jump to search
 
(24 intermediate revisions by 2 users not shown)
Line 1: Line 1:
== Abstract view ==
== Abstract view ==


This is a specialization of [[Preflow-push]]:
This is a specialization of the [[Preflow-push|generic preflow-push algorithm]]:
# The set of all active nodes is stored in a [[FIFO queue]] <math>Q</math>.
# The set of all [[Basic flow definitions#Preflow|active nodes]] is stored in a [[Sets and sequences#Stacks and queues|FIFO queue]] <math>Q</math>.
# While the first node in <math>Q</math> is active and has an admissible arc, choose this node.
# Always choose the first node in <math>Q</math> (recall from the generic preflow-push that this node is not extracted from <math>Q</math> as long as it is active).


== Complexity ==
== Complexity ==
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|</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 [[Preflow-push#Complexity|complexity considerations]] for the [[Preflow-push|generic preflow-push algorithm]] yield <math>\mathcal{O}(n^2)</math> relabel operations and forward steps of current arcs, and <math>\mathcal{O}(n\!\cdot\!m)\subseteq\mathcal{O}(n^3)</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 remains to show that the total number of non-saturating push operations is in <math>\mathcal{O}(n^3)</math> as well.


Conceptually, we may partition the algorithm into ''phases''.
Conceptually (that is, in our reasoning, not in the implementation), we may partition the iterations of the 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 of 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<2n</math>. Clearly, only relabel operations can increase <math>D</math>, and the sum of all increases of <math>D</math>, taken over all relabel operations, cannot increase <math>D</math> by more than <math>2n^2</math> in total.
 
This observation immediately implies that the number of phases in which at least one relabeling operation takes place, is in <math>\mathcal{O}(n^2)</math>. On the other hand, <math>D</math> is decreased in every phase ''without'' relabel operation, because in this case, all excess is pushed from each active node to a node with smaller <math>d</math>-label. Due to the bound <math>\mathcal{O}(n^2)</math> on all increases of <math>D</math>, the number of ''de''creases of <math>D</math> and, hence, the number of phases without relabel operations is in <math>\mathcal{O}(n^2)</math> as well. The claim now follows from the observation that, in each phase, at most one non-saturating push is performed with each node because a non-saturating push makes a node inactive.

Latest revision as of 09:20, 14 December 2015

Abstract view

This is a specialization of the generic preflow-push algorithm:

  1. The set of all active nodes is stored in a FIFO queue [math]\displaystyle{ Q }[/math].
  2. Always choose the first node in [math]\displaystyle{ Q }[/math] (recall from the generic preflow-push that this node is not extracted from [math]\displaystyle{ Q }[/math] as long as it is active).

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 forward steps of current arcs, and [math]\displaystyle{ \mathcal{O}(n\!\cdot\!m)\subseteq\mathcal{O}(n^3) }[/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 remains to show that the total number of non-saturating push operations is in [math]\displaystyle{ \mathcal{O}(n^3) }[/math] as well.

Conceptually (that is, in our reasoning, not in the implementation), we may partition the iterations of the 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 of 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\lt 2n }[/math]. Clearly, only relabel operations can increase [math]\displaystyle{ D }[/math], and the sum of all increases of [math]\displaystyle{ D }[/math], taken over all relabel operations, cannot increase [math]\displaystyle{ D }[/math] by more than [math]\displaystyle{ 2n^2 }[/math] in total.

This observation immediately implies that the number of phases in which at least one relabeling operation takes place, is in [math]\displaystyle{ \mathcal{O}(n^2) }[/math]. On the other hand, [math]\displaystyle{ D }[/math] is decreased in every phase without relabel operation, because in this case, all excess is pushed from each active node to a node with smaller [math]\displaystyle{ d }[/math]-label. Due to the bound [math]\displaystyle{ \mathcal{O}(n^2) }[/math] on all increases of [math]\displaystyle{ D }[/math], the number of decreases of [math]\displaystyle{ D }[/math] and, hence, the number of phases without relabel operations is in [math]\displaystyle{ \mathcal{O}(n^2) }[/math] as well. The claim now follows from the observation that, in each phase, at most one non-saturating push is performed with each node because a non-saturating push makes a node inactive.