Blossom algorithm: Difference between revisions

Revision as of 19:28, 7 August 2018

Revision as of 00:58, 13 January 2019

Line 16:

| volume = 17

| year = 1965

| pages = 449–467449–467

}}</ref> Given a general [[Graph (discrete 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. Unlike [[bipartite graph|bipartite]] matching, the key new idea is that an odd-length cycle in the graph (blossom) is contracted to a single vertex, with the search continuing iteratively in the contracted graph.