FIFO preflow-push: Difference between revisions
Jump to navigation
Jump to search
(Created page with "== Abstract view ==") |
|||
| Line 1: | Line 1: | ||
== Abstract view == | == Abstract view == | ||
This is a specialization of [[Preflow-push]]: | |||
# The set of all active nodes is stored in a [[FIFO queue]] <math>Q</math>. | |||
# While the first node in <math>Q</math> is active and has an admissible arc, choose this node. | |||
== Complexity == | |||
'''Statement:''' | |||
The asymptotic complexity is in <math>\mathcal{O}(n^3)</math>, where <math>n=|V|</math>. | |||
'''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>. | |||
Revision as of 17:56, 27 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]. Both function classes are subsets of [math]\displaystyle{ \mathcal{O}(n^3) }[/math].