FIFO preflow-push: Difference between revisions

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


This is a specialization of the generic [[Preflow-push|preflow-push algorithm]]:
This is a specialization of the [[Preflow-push|generic preflow-push algorithm]]:
# The set of all active nodes is stored in a [[Sets and sequences#Stacks and queues|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>.
# 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).
# 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).


Line 11: Line 11:


'''Proof:'''
'''Proof:'''
The [[Preflow-push#Complexity|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)\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.
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 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\leq 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</math> in total.
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 iteration 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.
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.