Maximum matching by Edmonds
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: