Blossom algorithm

In <a href="/facts/Graph_theory/VVPCd4TX">graph theory</a>, the blossom algorithm is an <a href="/facts/Algorithm/fnl5NmRt">algorithm</a> for constructing <a href="/facts/Maximum_matching/oKaChmBt">maximum matchings</a> on <a href="/facts/Graph_(discrete_mathematics)/kw3eIBUe">graphs</a>. The algorithm was developed by <a href="/facts/Jack_Edmonds/4bLnep3e">Jack Edmonds</a> in 1961, and published in 1965. Given a general <a href="/facts/Graph_(discrete_mathematics)/kw3eIBUe">graph</a> 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 <a href="/facts/Bipartite_graph/xWcXV9MB">bipartite</a> 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.
The algorithm runs in time <a href="/facts/Big_O_notation/weFFjSWg">O</a>(|E||V|2), where |E| is the number of <a href="/facts/Edge_(graph)/W0MqKkyE">edges</a> of the graph and |V| is its number of <a href="/facts/Vertex_(graph)/WhlWmL3o">vertices</a>. A better running time of 
 
 
 
 O
 (
 
 |
 
 E
 
 |
 
 
 
 
 |
 
 V
 
 |
 
 
 
 )
 
 
 {\displaystyle O(|E|{\sqrt {|V|}})}
 
 for the same task can be achieved with the much more complex algorithm of Micali and Vazirani.
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 <a href="/facts/Linear_programming/GduXFQxT">linear programming</a> polyhedral description of the matching <a href="/facts/Polytope/a76nXrL0">polytope</a>, yielding an algorithm for min-weight matching. 
As elaborated by <a href="/facts/Alexander_Schrijver/eJHJNRGz">Alexander Schrijver</a>, further significance of the result comes from the fact that this was the first polytope whose proof of integrality "does not simply follow just from <a href="/facts/Total_unimodularity/J6bRTkN4">total unimodularity</a>, and its description was a breakthrough in <a href="/facts/Polyhedral_combinatorics/oVFESPjJ">polyhedral combinatorics</a>."

Blossom algorithm open-in-new

Blossom algorithm