Maximum matching by Edmonds: Difference between revisions
Jump to navigation
Jump to search
| Line 1: | Line 1: | ||
== Abstract view == | == Abstract view == | ||
'''Algo''' | |||
'''Type of algorithm:''' recursion | |||
'''Invariant:''' | '''Invariant:''' | ||
| Line 9: | Line 13: | ||
'''Break condition:''' | '''Break condition:''' | ||
There is no more [[Matchings in graphs#Alternating and augmenting paths|augmenting path]]. | There is no more [[Matchings in graphs#Alternating and augmenting paths|augmenting path]]. | ||
== Induction basis == | == Induction basis == | ||
Revision as of 18:07, 21 November 2014
Abstract view
Algo
Type of algorithm: recursion
Invariant: The current selection [math]\displaystyle{ M }[/math] of edges is a matching.
Variant: Either the cardinality of [math]\displaystyle{ M }[/math] increases, or the number of nodes of [math]\displaystyle{ G }[/math] decreases.
Break condition: There is no more augmenting path.
Induction basis
Abstract view: Start with some matching, for example, the empty matching.
Induction step
Abstract view:
- Apply the modified graph search from the classical algorithm for the restriction to bipartite graphs.
- However, in addition, each node has a boolean label even/odd, which is set when the graph search sees the node for the very first time. More specifically, for each node this is the parity of the distance from the start node in the arborescence.
Implementation of step 1: