Preflow-push - Revision history

Weihe: /* Induction step */

2017-06-20T03:53:31Z

Induction step

← Older revision		Revision as of 03:53, 20 June 2017
Line 51:		Line 51:
	# While the current arc of <math>v</math> is not void and not [[Basic flow definitions#Valid distance labeling\|admissible]] either, move the current arc one step forward.		# While the current arc of <math>v</math> is not void and not [[Basic flow definitions#Valid distance labeling\|admissible]] either, move the current arc one step forward.
	# If the current arc of <math>v</math> is ''not'' void now but an (admissible) outgoing arc <math>(v,w)</math>, say:		# If the current arc of <math>v</math> is ''not'' void now but an (admissible) outgoing arc <math>(v,w)</math>, say:
	## If <math>w\neq s</math> and <math>e_f(w)=0</math>, insert <math>w</math> in <math>S</math>.		## If <math>w\neq s</math> and <math>w\neq t</math> and <math>e_f(w)=0</math>, insert <math>w</math> in <math>S</math>.
	## Increase the flow over <math>(v,w)</math> by the minimum of <math>e_f(v)</math> and the residual capacity of <math>(v,w)</math>.		## Increase the flow over <math>(v,w)</math> by the minimum of <math>e_f(v)</math> and the residual capacity of <math>(v,w)</math>.
	## Increase <math>e_f(w)</math> by that value and decrease <math>e_f(v)</math> by the same value.		## Increase <math>e_f(w)</math> by that value and decrease <math>e_f(v)</math> by the same value.

Weihe: /* Induction step */

2017-06-12T08:34:31Z

Induction step

← Older revision		Revision as of 08:34, 12 June 2017
Line 51:		Line 51:
	# While the current arc of <math>v</math> is not void and not [[Basic flow definitions#Valid distance labeling\|admissible]] either, move the current arc one step forward.		# While the current arc of <math>v</math> is not void and not [[Basic flow definitions#Valid distance labeling\|admissible]] either, move the current arc one step forward.
	# If the current arc of <math>v</math> is ''not'' void now but an (admissible) outgoing arc <math>(v,w)</math>, say:		# If the current arc of <math>v</math> is ''not'' void now but an (admissible) outgoing arc <math>(v,w)</math>, say:
	## If <math>w\neq s,t</math> and <math>e_f(w)=0</math>, insert <math>w</math> in <math>S</math>.		## If <math>w\neq s</math> and <math>e_f(w)=0</math>, insert <math>w</math> in <math>S</math>.
	## Increase the flow over <math>(v,w)</math> by the minimum of <math>e_f(v)</math> and the residual capacity of <math>(v,w)</math>.		## Increase the flow over <math>(v,w)</math> by the minimum of <math>e_f(v)</math> and the residual capacity of <math>(v,w)</math>.
	## Increase <math>e_f(w)</math> by that value and decrease <math>e_f(v)</math> by the same value.		## Increase <math>e_f(w)</math> by that value and decrease <math>e_f(v)</math> by the same value.

Weihe: /* Induction step */

2017-06-12T08:33:02Z

Induction step

← Older revision		Revision as of 08:33, 12 June 2017
Line 51:		Line 51:
	# While the current arc of <math>v</math> is not void and not [[Basic flow definitions#Valid distance labeling\|admissible]] either, move the current arc one step forward.		# While the current arc of <math>v</math> is not void and not [[Basic flow definitions#Valid distance labeling\|admissible]] either, move the current arc one step forward.
	# If the current arc of <math>v</math> is ''not'' void now but an (admissible) outgoing arc <math>(v,w)</math>, say:		# If the current arc of <math>v</math> is ''not'' void now but an (admissible) outgoing arc <math>(v,w)</math>, say:
	## If <math>w\neq s</math> and <math>e_f(w)=0</math>, insert <math>w</math> in <math>S</math>.		## If <math>w\neq s,t</math> and <math>e_f(w)=0</math>, insert <math>w</math> in <math>S</math>.
	## Increase the flow over <math>(v,w)</math> by the minimum of <math>e_f(v)</math> and the residual capacity of <math>(v,w)</math>.		## Increase the flow over <math>(v,w)</math> by the minimum of <math>e_f(v)</math> and the residual capacity of <math>(v,w)</math>.
	## Increase <math>e_f(w)</math> by that value and decrease <math>e_f(v)</math> by the same value.		## Increase <math>e_f(w)</math> by that value and decrease <math>e_f(v)</math> by the same value.

Weihe: /* Induction step */

2017-06-12T08:32:19Z

Induction step

← Older revision		Revision as of 08:32, 12 June 2017
Line 51:		Line 51:
	# While the current arc of <math>v</math> is not void and not [[Basic flow definitions#Valid distance labeling\|admissible]] either, move the current arc one step forward.		# While the current arc of <math>v</math> is not void and not [[Basic flow definitions#Valid distance labeling\|admissible]] either, move the current arc one step forward.
	# If the current arc of <math>v</math> is ''not'' void now but an (admissible) outgoing arc <math>(v,w)</math>, say:		# If the current arc of <math>v</math> is ''not'' void now but an (admissible) outgoing arc <math>(v,w)</math>, say:
	## If <math>w\neq s</math> ~~and and~~ and <math>e_f(w)=0</math>, insert <math>w</math> in <math>S</math>.		## If <math>w\neq s</math> and <math>e_f(w)=0</math>, insert <math>w</math> in <math>S</math>.
	## Increase the flow over <math>(v,w)</math> by the minimum of <math>e_f(v)</math> and the residual capacity of <math>(v,w)</math>.		## Increase the flow over <math>(v,w)</math> by the minimum of <math>e_f(v)</math> and the residual capacity of <math>(v,w)</math>.
	## Increase <math>e_f(w)</math> by that value and decrease <math>e_f(v)</math> by the same value.		## Increase <math>e_f(w)</math> by that value and decrease <math>e_f(v)</math> by the same value.

Weihe: /* Induction step */

2017-06-12T08:32:05Z

Induction step

← Older revision		Revision as of 08:32, 12 June 2017
Line 51:		Line 51:
	# While the current arc of <math>v</math> is not void and not [[Basic flow definitions#Valid distance labeling\|admissible]] either, move the current arc one step forward.		# While the current arc of <math>v</math> is not void and not [[Basic flow definitions#Valid distance labeling\|admissible]] either, move the current arc one step forward.
	# If the current arc of <math>v</math> is ''not'' void now but an (admissible) outgoing arc <math>(v,w)</math>, say:		# If the current arc of <math>v</math> is ''not'' void now but an (admissible) outgoing arc <math>(v,w)</math>, say:
	## If <math>w\neq s</math> and <math>e_f(w)=0</math>, insert <math>w</math> in <math>S</math>.		## If <math>w\neq s</math> and and and <math>e_f(w)=0</math>, insert <math>w</math> in <math>S</math>.
	## Increase the flow over <math>(v,w)</math> by the minimum of <math>e_f(v)</math> and the residual capacity of <math>(v,w)</math>.		## Increase the flow over <math>(v,w)</math> by the minimum of <math>e_f(v)</math> and the residual capacity of <math>(v,w)</math>.
	## Increase <math>e_f(w)</math> by that value and decrease <math>e_f(v)</math> by the same value.		## Increase <math>e_f(w)</math> by that value and decrease <math>e_f(v)</math> by the same value.

Weihe: /* Induction step */

2017-06-12T08:30:08Z

Induction step

← Older revision		Revision as of 08:30, 12 June 2017
Line 51:		Line 51:
	# While the current arc of <math>v</math> is not void and not [[Basic flow definitions#Valid distance labeling\|admissible]] either, move the current arc one step forward.		# While the current arc of <math>v</math> is not void and not [[Basic flow definitions#Valid distance labeling\|admissible]] either, move the current arc one step forward.
	# If the current arc of <math>v</math> is ''not'' void now but an (admissible) outgoing arc <math>(v,w)</math>, say:		# If the current arc of <math>v</math> is ''not'' void now but an (admissible) outgoing arc <math>(v,w)</math>, say:
	## If <math>w\neq t</math> and <math>e_f(w)=0</math>, insert <math>w</math> in <math>S</math>.		## If <math>w\neq s</math> and <math>e_f(w)=0</math>, insert <math>w</math> in <math>S</math>.
	## Increase the flow over <math>(v,w)</math> by the minimum of <math>e_f(v)</math> and the residual capacity of <math>(v,w)</math>.		## Increase the flow over <math>(v,w)</math> by the minimum of <math>e_f(v)</math> and the residual capacity of <math>(v,w)</math>.
	## Increase <math>e_f(w)</math> by that value and decrease <math>e_f(v)</math> by the same value.		## Increase <math>e_f(w)</math> by that value and decrease <math>e_f(v)</math> by the same value.

Weihe: /* Induction step */

2017-06-12T08:29:58Z

Induction step

← Older revision		Revision as of 08:29, 12 June 2017
Line 51:		Line 51:
	# While the current arc of <math>v</math> is not void and not [[Basic flow definitions#Valid distance labeling\|admissible]] either, move the current arc one step forward.		# While the current arc of <math>v</math> is not void and not [[Basic flow definitions#Valid distance labeling\|admissible]] either, move the current arc one step forward.
	# If the current arc of <math>v</math> is ''not'' void now but an (admissible) outgoing arc <math>(v,w)</math>, say:		# If the current arc of <math>v</math> is ''not'' void now but an (admissible) outgoing arc <math>(v,w)</math>, say:
	## If <math>w\neq s</math> and <math>e_f(w)=0</math>, insert <math>w</math> in <math>S</math>.		## If <math>w\neq t</math> and <math>e_f(w)=0</math>, insert <math>w</math> in <math>S</math>.
	## Increase the flow over <math>(v,w)</math> by the minimum of <math>e_f(v)</math> and the residual capacity of <math>(v,w)</math>.		## Increase the flow over <math>(v,w)</math> by the minimum of <math>e_f(v)</math> and the residual capacity of <math>(v,w)</math>.
	## Increase <math>e_f(w)</math> by that value and decrease <math>e_f(v)</math> by the same value.		## Increase <math>e_f(w)</math> by that value and decrease <math>e_f(v)</math> by the same value.

Weihe: /* Induction step */

2017-06-12T08:29:38Z

Induction step

← Older revision		Revision as of 08:29, 12 June 2017
Line 51:		Line 51:
	# While the current arc of <math>v</math> is not void and not [[Basic flow definitions#Valid distance labeling\|admissible]] either, move the current arc one step forward.		# While the current arc of <math>v</math> is not void and not [[Basic flow definitions#Valid distance labeling\|admissible]] either, move the current arc one step forward.
	# If the current arc of <math>v</math> is ''not'' void now but an (admissible) outgoing arc <math>(v,w)</math>, say:		# If the current arc of <math>v</math> is ''not'' void now but an (admissible) outgoing arc <math>(v,w)</math>, say:
	## If <math>w\neq s,t</math> and <math>e_f(w)=0</math>, insert <math>w</math> in <math>S</math>.		## If <math>w\neq s</math> and <math>e_f(w)=0</math>, insert <math>w</math> in <math>S</math>.
	## Increase the flow over <math>(v,w)</math> by the minimum of <math>e_f(v)</math> and the residual capacity of <math>(v,w)</math>.		## Increase the flow over <math>(v,w)</math> by the minimum of <math>e_f(v)</math> and the residual capacity of <math>(v,w)</math>.
	## Increase <math>e_f(w)</math> by that value and decrease <math>e_f(v)</math> by the same value.		## Increase <math>e_f(w)</math> by that value and decrease <math>e_f(v)</math> by the same value.

Weihe: /* Induction step */

2017-06-12T08:29:18Z

Induction step

← Older revision		Revision as of 08:29, 12 June 2017
Line 51:		Line 51:
	# While the current arc of <math>v</math> is not void and not [[Basic flow definitions#Valid distance labeling\|admissible]] either, move the current arc one step forward.		# While the current arc of <math>v</math> is not void and not [[Basic flow definitions#Valid distance labeling\|admissible]] either, move the current arc one step forward.
	# If the current arc of <math>v</math> is ''not'' void now but an (admissible) outgoing arc <math>(v,w)</math>, say:		# If the current arc of <math>v</math> is ''not'' void now but an (admissible) outgoing arc <math>(v,w)</math>, say:
	## If <math>w\neq s~~</math> and <math>w\neq~~ t</math> and <math>e_f(w)=0</math>, insert <math>w</math> in <math>S</math>.		## If <math>w\neq s,t</math> and <math>e_f(w)=0</math>, insert <math>w</math> in <math>S</math>.
	## Increase the flow over <math>(v,w)</math> by the minimum of <math>e_f(v)</math> and the residual capacity of <math>(v,w)</math>.		## Increase the flow over <math>(v,w)</math> by the minimum of <math>e_f(v)</math> and the residual capacity of <math>(v,w)</math>.
	## Increase <math>e_f(w)</math> by that value and decrease <math>e_f(v)</math> by the same value.		## Increase <math>e_f(w)</math> by that value and decrease <math>e_f(v)</math> by the same value.

Weihe: /* Induction step */

2017-06-12T08:28:49Z

Induction step

← Older revision		Revision as of 08:28, 12 June 2017
Line 51:		Line 51:
	# While the current arc of <math>v</math> is not void and not [[Basic flow definitions#Valid distance labeling\|admissible]] either, move the current arc one step forward.		# While the current arc of <math>v</math> is not void and not [[Basic flow definitions#Valid distance labeling\|admissible]] either, move the current arc one step forward.
	# If the current arc of <math>v</math> is ''not'' void now but an (admissible) outgoing arc <math>(v,w)</math>, say:		# If the current arc of <math>v</math> is ''not'' void now but an (admissible) outgoing arc <math>(v,w)</math>, say:
	## If <math>w\neq s</math> and <math>e_f(w)=0</math>, insert <math>w</math> in <math>S</math>.		## If <math>w\neq s</math> and <math>w\neq t</math> and <math>e_f(w)=0</math>, insert <math>w</math> in <math>S</math>.
	## Increase the flow over <math>(v,w)</math> by the minimum of <math>e_f(v)</math> and the residual capacity of <math>(v,w)</math>.		## Increase the flow over <math>(v,w)</math> by the minimum of <math>e_f(v)</math> and the residual capacity of <math>(v,w)</math>.
	## Increase <math>e_f(w)</math> by that value and decrease <math>e_f(v)</math> by the same value.		## Increase <math>e_f(w)</math> by that value and decrease <math>e_f(v)</math> by the same value.