FIFO preflow-push - Revision history

Weihe: /* Complexity */

2015-12-14T09:20:57Z

Complexity

← Older revision		Revision as of 09:20, 14 December 2015
Line 15:		Line 15:
	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.		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.		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.

Weihe: /* Complexity */

2015-12-14T09:20:08Z

Complexity

← Older revision		Revision as of 09:20, 14 December 2015
Line 13:		Line 13:
	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.		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<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.		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.		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.

BB91: /* Complexity */

2015-02-04T17:56:25Z

Complexity

← Older revision		Revision as of 17:56, 4 February 2015
Line 15:		Line 15:
	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<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.		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<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.

Weihe: /* Complexity */

2014-12-01T14:00:27Z

Complexity

← Older revision		Revision as of 14:00, 1 December 2014
Line 13:		Line 13:
	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.		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\<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.		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<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 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.

Weihe: /* Complexity */

2014-12-01T14:00:10Z

Complexity

← Older revision		Revision as of 14:00, 1 December 2014
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^2</math> in total.		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\<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 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.

Weihe: /* Abstract view */

2014-12-01T13:58:22Z

Abstract view

← Older revision		Revision as of 13:58, 1 December 2014
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).

Weihe at 13:16, 10 November 2014

2014-11-10T13:16:09Z

← Older revision		Revision as of 13:16, 10 November 2014
Line 13:		Line 13:
	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 <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, 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^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 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.

Weihe: /* Complexity */

2014-11-10T13:08:10Z

Complexity

← Older revision		Revision as of 13:08, 10 November 2014
Line 15:		Line 15:
	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, 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.

	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)</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 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.

Weihe: /* Complexity */

2014-11-10T13:07:19Z

Complexity

← Older revision		Revision as of 13:07, 10 November 2014
Line 13:		Line 13:
	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 <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>~~\Delta~~</math>, and the sum of all increases of <math>~~\Delta~~</math>, taken over all relabel operations, cannot increase <math>~~\Delta~~</math> by more than <math>2n</math> in total.		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.

	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)</math> on all increases of <math>~~\Delta~~</math>, the number of ''de''creases of <math>~~\Delta~~</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 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)</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.

Weihe: /* Complexity */

2014-11-10T13:06:11Z

Complexity

← Older revision		Revision as of 13:06, 10 November 2014
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>.		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.

	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>\Delta</math>, and the sum of all increases of <math>\Delta</math>, taken over all relabel operations, cannot increase <math>\Delta</math> by more than <math>2n</math> in total.		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>\Delta</math>, and the sum of all increases of <math>\Delta</math>, taken over all relabel operations, cannot increase <math>\Delta</math> by more than <math>2n</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)</math> on all increases of <math>\Delta</math>, the number of ''de''creases of <math>\Delta</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 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)</math> on all increases of <math>\Delta</math>, the number of ''de''creases of <math>\Delta</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.