Blossom algorithm: Difference between revisions

Revision as of 14:35, 31 January 2016

Revision as of 19:58, 31 January 2016

Line 17:

| year = 1965

| pages = 449–467

}}</ref> Given a general [[Graph (discrete mathematics)|graph]]{{dn|date=January 2016}} ''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.

A major reason that the blossom algorithm is important is that it gave the first proof that a maximum-size matching could be found using a polynomial amount of computation time. Another reason is that it led to a [[linear programming]] polyhedral description of the matching [[polytope]], yielding an algorithm for min-''weight'' matching.<ref name = "weighted">