Three indians' algorithm - Revision history

Weihe: /* Induction step */

2017-03-16T11:27:41Z

Induction step

← Older revision		Revision as of 11:27, 16 March 2017
Line 41:		Line 41:
	## If <math>u(v,w)=0</math>, remove <math>(v,w)</math> from <math>G</math>.		## If <math>u(v,w)=0</math>, remove <math>(v,w)</math> from <math>G</math>.
	## If <math>F(v)=0</math>, finish this iteration.		## If <math>F(v)=0</math>, finish this iteration.
	# Run steps 4+5 from <math>v_0</math> on the [[Basic graph definitions#Transpose of a graph\|transpose]] of <math>G</math> with the value of <math>~~T_0~~</math> as computed in step 1 (all removals apply to <math>G</math>).		# Run steps 4+5 from <math>v_0</math> on the [[Basic graph definitions#Transpose of a graph\|transpose]] of <math>G</math> with the value of <math>T(v_0)</math> as computed in step 1 (all removals apply to <math>G</math>).

	'''Proof:'''		'''Proof:'''

Weihe: /* Induction step */

2017-03-16T11:26:41Z

Induction step

← Older revision		Revision as of 11:26, 16 March 2017
Line 41:		Line 41:
	## If <math>u(v,w)=0</math>, remove <math>(v,w)</math> from <math>G</math>.		## If <math>u(v,w)=0</math>, remove <math>(v,w)</math> from <math>G</math>.
	## If <math>F(v)=0</math>, finish this iteration.		## If <math>F(v)=0</math>, finish this iteration.
	# Run steps 4+5 from <math>v_0</math> on the [[Basic graph definitions#Transpose of a graph\|transpose]] of <math>G</math> with the value of <math>T</math> computed in step 1 (all removals apply to <math>G</math>).		# Run steps 4+5 from <math>v_0</math> on the [[Basic graph definitions#Transpose of a graph\|transpose]] of <math>G</math> with the value of <math>T_0</math> as computed in step 1 (all removals apply to <math>G</math>).

	'''Proof:'''		'''Proof:'''

Weihe: /* Induction step */

2017-03-16T11:26:24Z

Induction step

← Older revision		Revision as of 11:26, 16 March 2017
Line 41:		Line 41:
	## If <math>u(v,w)=0</math>, remove <math>(v,w)</math> from <math>G</math>.		## If <math>u(v,w)=0</math>, remove <math>(v,w)</math> from <math>G</math>.
	## If <math>F(v)=0</math>, finish this iteration.		## If <math>F(v)=0</math>, finish this iteration.
	# Run steps 4+5 from <math>v_0</math> on the [[Basic graph definitions#Transpose of a graph\|transpose]] of <math>G</math> with the value of computed in step 1 (all removals apply to <math>G</math>).		# Run steps 4+5 from <math>v_0</math> on the [[Basic graph definitions#Transpose of a graph\|transpose]] of <math>G</math> with the value of <math>T</math> computed in step 1 (all removals apply to <math>G</math>).

	'''Proof:'''		'''Proof:'''

Weihe: /* Induction step */

2017-03-16T11:25:18Z

Induction step

← Older revision		Revision as of 11:25, 16 March 2017
Line 41:		Line 41:
	## If <math>u(v,w)=0</math>, remove <math>(v,w)</math> from <math>G</math>.		## If <math>u(v,w)=0</math>, remove <math>(v,w)</math> from <math>G</math>.
	## If <math>F(v)=0</math>, finish this iteration.		## If <math>F(v)=0</math>, finish this iteration.
	# Run steps 4+5 from <math>v_0</math> on the [[Basic graph definitions#Transpose of a graph\|transpose]] of <math>G</math> with the value of .		# Run steps 4+5 from <math>v_0</math> on the [[Basic graph definitions#Transpose of a graph\|transpose]] of <math>G</math> with the value of computed in step 1 (all removals apply to <math>G</math>).

	'''Proof:'''		'''Proof:'''

Weihe: /* Induction step */

2017-03-16T11:24:56Z

Induction step

← Older revision		Revision as of 11:24, 16 March 2017
Line 41:		Line 41:
	## If <math>u(v,w)=0</math>, remove <math>(v,w)</math> from <math>G</math>.		## If <math>u(v,w)=0</math>, remove <math>(v,w)</math> from <math>G</math>.
	## If <math>F(v)=0</math>, finish this iteration.		## If <math>F(v)=0</math>, finish this iteration.
	# Run steps 4+5 from <math>v_0</math> on the [[Basic graph definitions#Transpose of a graph\|transpose]] of <math>G</math> with the value of ~~<math>T_0</math> computed in step 1 (all removals apply to <math>G</math>)~~.		# Run steps 4+5 from <math>v_0</math> on the [[Basic graph definitions#Transpose of a graph\|transpose]] of <math>G</math> with the value of .

	'''Proof:'''		'''Proof:'''

Weihe: /* Induction step */

2017-03-16T11:24:01Z

Induction step

← Older revision		Revision as of 11:24, 16 March 2017
Line 41:		Line 41:
	## If <math>u(v,w)=0</math>, remove <math>(v,w)</math> from <math>G</math>.		## If <math>u(v,w)=0</math>, remove <math>(v,w)</math> from <math>G</math>.
	## If <math>F(v)=0</math>, finish this iteration.		## If <math>F(v)=0</math>, finish this iteration.
	# Run ~~the same modified [[Breadth-first search\|BFS]]~~ from <math>v_0</math> on the [[Basic graph definitions#Transpose of a graph\|transpose]] of <math>G</math> (all removals apply to <math>G</math>).		# Run steps 4+5 from <math>v_0</math> on the [[Basic graph definitions#Transpose of a graph\|transpose]] of <math>G</math> with the value of <math>T_0</math> computed in step 1 (all removals apply to <math>G</math>).

	'''Proof:'''		'''Proof:'''

BB91: /* Induction step */

2015-02-16T13:30:38Z

Induction step

← Older revision		Revision as of 13:30, 16 February 2015
Line 30:		Line 30:

	'''Implementation:'''		'''Implementation:'''
	# For each node <math>v\in V\setminus\{s,t\}</math>, let <math>T(v)</math> ~~denoet~~ the '''throughput''' of <math>v</math>, which is defined by <math>T(v):=\min\left\{\sum_{w:(v,w)\in A}u(v,w),\sum_{w:(w,v)\in A}u(w,v)\right\}</math>.		# For each node <math>v\in V\setminus\{s,t\}</math>, let <math>T(v)</math> denote the '''throughput''' of <math>v</math>, which is defined by <math>T(v):=\min\left\{\sum_{w:(v,w)\in A}u(v,w),\sum_{w:(w,v)\in A}u(w,v)\right\}</math>.
	# Remove all nodes with zero throughput and all arcs incident to at least one of these nodes.		# Remove all nodes with zero throughput and all arcs incident to at least one of these nodes.
	# Let <math>v_0\in V\setminus\{s,t\}</math> be a node with minimum throughput <math>T(v_0)</math>.		# Let <math>v_0\in V\setminus\{s,t\}</math> be a node with minimum throughput <math>T(v_0)</math>.

Weihe: /* Remarks */

2014-11-10T11:14:40Z

Remarks

← Older revision		Revision as of 11:14, 10 November 2014
Line 61:		Line 61:

	# The algorithm is named after three indian researchers, V. M. Malhotra, M. Pramodh Kumar, and S. N. Mahashwari.		# The algorithm is named after three indian researchers, V. M. Malhotra, M. Pramodh Kumar, and S. N. Mahashwari.
	# Of course, the nodes and arcs need not really be removed from the graph. However, "removed" nodes and arcs must be hidden from the algorithm to ensure the asymptotic complexity; a Boolean ~~lable~~ "is removed" does not suffice for that.		# Of course, the nodes and arcs need not really be removed from the graph. However, "removed" nodes and arcs must be hidden from the algorithm to ensure the asymptotic complexity; a Boolean label "is removed" does not suffice for that.
	# This application of [[Breadth-first search\|BFS]] is an example for one of the remarks on [[Graph traversal#Remarks\|graph traversal]]: It is reasonable to implement graph-traversal algorithms as iterators. In fact, then the modification may be simply added to the loop that runs the iterator.		# This application of [[Breadth-first search\|BFS]] is an example for one of the remarks on [[Graph traversal#Remarks\|graph traversal]]: It is reasonable to implement graph-traversal algorithms as iterators. In fact, then the modification may be simply added to the loop that runs the iterator.

Weihe: /* Complexity */

2014-11-10T11:13:56Z

Complexity

← Older revision		Revision as of 11:13, 10 November 2014
Line 56:		Line 56:

	'''Proof:'''		'''Proof:'''
	Due to the variant, the number of iterations is linear in <math>n</math>. When an arc is saturated, it is removed, so the total number of saturating increases of flow values of arcs over all iterations of the main loop is linear in the number of arcs, which is in <math>\mathcal{O}(n^2)</math>. In each execution of step 5 (resp., step 6), the flow on at most one outgoing (incoming) arc of each node is increased without saturation, so the number of non-saturating ~~increases~~ is linear in the number of nodes in each iteration.		Due to the variant, the number of iterations is linear in <math>n</math>. When an arc is saturated, it is removed in step 5.5 (resp., 6.5), so the total number of saturating increases of flow values of arcs over all iterations of the main loop is linear in the number of arcs, which is in <math>\mathcal{O}(n^2)</math>. In each execution of step 5 (resp., step 6), the flow on at most one outgoing (resp., incoming) arc of each node is increased without saturation, so the number of ''non''-saturating flow value settings is linear in the number of nodes in each iteration.

	== Remarks ==		== Remarks ==

Weihe: /* Induction step */

2014-11-10T11:12:23Z

Induction step

← Older revision		Revision as of 11:12, 10 November 2014
Line 40:		Line 40:
	## Decrease <math>F(v)</math>, <math>T(v)</math>, and <math>u(v,w)</math> by <math>\Delta</math>.		## Decrease <math>F(v)</math>, <math>T(v)</math>, and <math>u(v,w)</math> by <math>\Delta</math>.
	## If <math>u(v,w)=0</math>, remove <math>(v,w)</math> from <math>G</math>.		## If <math>u(v,w)=0</math>, remove <math>(v,w)</math> from <math>G</math>.
			## If <math>F(v)=0</math>, finish this iteration.
	# Run the same modified [[Breadth-first search\|BFS]] from <math>v_0</math> on the [[Basic graph definitions#Transpose of a graph\|transpose]] of <math>G</math> (all removals apply to <math>G</math>).		# Run the same modified [[Breadth-first search\|BFS]] from <math>v_0</math> on the [[Basic graph definitions#Transpose of a graph\|transpose]] of <math>G</math> (all removals apply to <math>G</math>).