Alternating paths algorithm - Revision history

JanR at 13:38, 27 January 2015

2015-01-27T13:38:33Z

← Older revision		Revision as of 13:38, 27 January 2015
Line 2:		Line 2:
	[[Category:Maximum matching problem]]		[[Category:Maximum matching problem]]

	'''Algorithmic Problem:''' [[~~Maximum matching problem~~]].		'''Algorithmic Problem:''' [[Matchings in graphs]].

	'''Prerequisites:''' The graph <math>G</math> is [[Bipartite graph\|bipartite]].		'''Prerequisites:''' The graph <math>G</math> is [[Bipartite graph\|bipartite]].

JanR at 13:25, 27 January 2015

2015-01-27T13:25:59Z

← Older revision		Revision as of 13:25, 27 January 2015
Line 2:		Line 2:
	[[Category:Maximum matching problem]]		[[Category:Maximum matching problem]]

	'''Algorithmic Problem:''' [~~http://wiki.algo.informatik.tu-darmstadt.de/index.php/Matchings_in_graphs#Cardinality-maximal_matching\~~ Maximum matching problem]		'''Algorithmic Problem:''' [[Maximum matching problem]].

	'''Prerequisites:''' The graph <math>G</math> is [~~http://wiki.algo.informatik.tu-darmstadt.de/index.php/Bipartite_graph\~~ bipartite].		'''Prerequisites:''' The graph <math>G</math> is [[Bipartite graph\|bipartite]].

	'''Type of algorithm:''' loop		'''Type of algorithm:''' loop

JanR at 13:21, 27 January 2015

2015-01-27T13:21:21Z

← Older revision		Revision as of 13:21, 27 January 2015
Line 3:		Line 3:

	'''Algorithmic Problem:''' [http://wiki.algo.informatik.tu-darmstadt.de/index.php/Matchings_in_graphs#Cardinality-maximal_matching\ Maximum matching problem]		'''Algorithmic Problem:''' [http://wiki.algo.informatik.tu-darmstadt.de/index.php/Matchings_in_graphs#Cardinality-maximal_matching\ Maximum matching problem]

	'''Prerequisites:''' The graph <math>G</math> is [http://wiki.algo.informatik.tu-darmstadt.de/index.php/Bipartite_graph\ bipartite].		'''Prerequisites:''' The graph <math>G</math> is [http://wiki.algo.informatik.tu-darmstadt.de/index.php/Bipartite_graph\ bipartite].

JanR at 13:21, 27 January 2015

2015-01-27T13:21:09Z

← Older revision		Revision as of 13:21, 27 January 2015
Line 2:		Line 2:
	[[Category:Maximum matching problem]]		[[Category:Maximum matching problem]]

			'''Algorithmic Problem:''' [http://wiki.algo.informatik.tu-darmstadt.de/index.php/Matchings_in_graphs#Cardinality-maximal_matching\ Maximum matching problem]
	'''Algorithmic problem:''' The graph <math>G</math> is ~~biparite~~.		'''Prerequisites:''' The graph <math>G</math> is [http://wiki.algo.informatik.tu-darmstadt.de/index.php/Bipartite_graph\ bipartite].

	'''Type of algorithm:''' loop		'''Type of algorithm:''' loop

JanR at 13:18, 27 January 2015

2015-01-27T13:18:15Z

← Older revision		Revision as of 13:18, 27 January 2015
Line 19:		Line 19:
	== Induction basis ==		== Induction basis ==

	'''Abstract view:''' <math>M</math> is initialized to be some matching, for example, <math>M:=\~~empty1~~</math>.		'''Abstract view:''' <math>M</math> is initialized to be some matching, for example, <math>M:=\empty</math>.

	'''Implementation:''' Obvious.		'''Implementation:''' Obvious.
Line 33:		Line 33:
	# If this call fails, terminate the algorithm and return <math>M</math>.		# If this call fails, terminate the algorithm and return <math>M</math>.
	# Otherwise, let <math>E'</math> denote the set of all edges on the path delivered by that call.		# Otherwise, let <math>E'</math> denote the set of all edges on the path delivered by that call.
	# Let <math>M</math> be the [http://en.wikipedia.org/wiki/Symmetric_difference symmetric difference] of <math>M</math> and <math<???</math>		# Let <math>M</math> be the [http://en.wikipedia.org/wiki/Symmetric_difference symmetric difference] of <math>M</math> and <math>???</math>
	Correctness:		Correctness:

JanR at 13:16, 27 January 2015

2015-01-27T13:16:47Z

← Older revision		Revision as of 13:16, 27 January 2015
Line 3:		Line 3:


	'''Algorithmic problem:''' The graph <math>G</math> is biparite.		'''Algorithmic problem:''' The graph <math>G</math> is biparite.

	'''Type of algorithm:''' loop		'''Type of algorithm:''' loop

	'''Auxillary data:'''		'''Auxillary data:'''

	== Abstract view ==		== Abstract view ==

	'''Invariant:''' Before and after each iteration, <math>M</math> is a matching.		'''Invariant:''' Before and after each iteration, <math>M</math> is a matching.

	'''Variant:''' <math>\|M\|</math> increases by <math>1</math>.		'''Variant:''' <math>\|M\|</math> increases by <math>1</math>.

	'''Break condition:''' There is no more augmenting alternating path.		'''Break condition:''' There is no more augmenting alternating path.

	== Induction basis ==		== Induction basis ==

	'''Abstract view:''' <math>M</math> is initialized to be some matching, for example, <math>M:=\empty1</math>.		'''Abstract view:''' <math>M</math> is initialized to be some matching, for example, <math>M:=\empty1</math>.

	'''Implementation:''' Obvious.		'''Implementation:''' Obvious.

	'''Proof:''' Nothing to show.		'''Proof:''' Nothing to show.

	== Induction step ==		== Induction step ==

	'''Abstract view:''' If there is an augmenting alternating path, use it to increase <math>M</math>; otherwise, terminate the algorithm and return <math>M</math>.		'''Abstract view:''' If there is an augmenting alternating path, use it to increase <math>M</math>; otherwise, terminate the algorithm and return <math>M</math>.

	'''Implementation:'''		'''Implementation:'''
	# Call the algorithm Find augmenting alternating path.		# Call the algorithm Find augmenting alternating path.
	# If this call fails, terminate the algorithm and return <math>M</math>.		# If this call fails, terminate the algorithm and return <math>M</math>.

JanR at 13:16, 27 January 2015

2015-01-27T13:16:17Z

← Older revision		Revision as of 13:16, 27 January 2015
Line 4:		Line 4:

	'''Algorithmic problem:''' The graph <math>G</math> is biparite.		'''Algorithmic problem:''' The graph <math>G</math> is biparite.

	'''Type of algorithm:''' loop		'''Type of algorithm:''' loop

	'''Auxillary data:'''		'''Auxillary data:'''

Line 10:		Line 12:

	'''Invariant:''' Before and after each iteration, <math>M</math> is a matching.		'''Invariant:''' Before and after each iteration, <math>M</math> is a matching.

	'''Variant:''' <math>\|M\|</math> increases by <math>1</math>.		'''Variant:''' <math>\|M\|</math> increases by <math>1</math>.

	'''Break condition:''' There is no more augmenting alternating path.		'''Break condition:''' There is no more augmenting alternating path.

Line 16:		Line 20:

	'''Abstract view:''' <math>M</math> is initialized to be some matching, for example, <math>M:=\empty1</math>.		'''Abstract view:''' <math>M</math> is initialized to be some matching, for example, <math>M:=\empty1</math>.

	'''Implementation:''' Obvious.		'''Implementation:''' Obvious.

	'''Proof:''' Nothing to show.		'''Proof:''' Nothing to show.

Line 22:		Line 28:

	'''Abstract view:''' If there is an augmenting alternating path, use it to increase <math>M</math>; otherwise, terminate the algorithm and return <math>M</math>.		'''Abstract view:''' If there is an augmenting alternating path, use it to increase <math>M</math>; otherwise, terminate the algorithm and return <math>M</math>.

	'''Implementation:'''		'''Implementation:'''
	# Call the algorithm Find augmenting alternating path.		# Call the algorithm Find augmenting alternating path.

JanR: /* Complexity */

2015-01-27T13:15:51Z

Complexity

← Older revision		Revision as of 13:15, 27 January 2015
Line 32:		Line 32:

	'''Statement:'''		'''Statement:'''

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

	==Further information==		==Further information==

JanR: /* Complexity */

2015-01-27T13:15:42Z

Complexity

← Older revision		Revision as of 13:15, 27 January 2015
Line 31:		Line 31:
	== Complexity ==		== Complexity ==

	'''Statement:'''		'''Statement:'''
	'''Proof:'''		'''Proof:'''

	==Further information==		==Further information==

JanR at 13:15, 27 January 2015

2015-01-27T13:15:26Z

← Older revision		Revision as of 13:15, 27 January 2015
Line 15:		Line 15:
	== Induction basis ==		== Induction basis ==

	'''Abstract view:''' <math>M</math> is initialized to be some matching, for example, <math>M:=\empty1</math>.		'''Abstract view:''' <math>M</math> is initialized to be some matching, for example, <math>M:=\empty1</math>.
	'''Implementation:''' Obvious.		'''Implementation:''' Obvious.
	'''Proof:''' Nothing to show.		'''Proof:''' Nothing to show.

	== Induction step ==		== Induction step ==