Blossom algorithm: Difference between revisions

Revision as of 15:36, 28 February 2011

Revision as of 15:28, 19 May 2011

Line 10:

| pages = 449–467

}}</ref>

is an [[algorithm]] in [[graph theory]] for constructing [[maximum matching]]s on graphs. The algorithm was discovered by [[Jack Edmonds]] in 1965. Given a general [[graph (mathematics)|graph]] ''G'' = (''V'', ''E''), the algorithm finds a matching ''M'' such that each vertex in ''V'' is incident with at most one edge in ''M'' and |''M''| is maximized. The matching is constructed by iteratively improving an initial empty matching along augmenting paths in the graph. To search for augmenting paths, some odd-length cycles in the graph (blossoms) are contracted to single vertices and the search continues recursively in the contracted graphs.

==Augmenting paths==