{{short description|Algorithm for finding max graph matchings}}
The '''blossom algorithm''' is an [[algorithm]] in [[graph theory]] for constructing [[maximum matching]]s on graphs. The algorithm was developed by [[Jack Edmonds]] in 1961,<ref name = "glimpse">{{Citation▼
▲TheIn [[graph theory]], the '''blossom algorithm''' is an [[algorithm]] in [[graph theory]] for constructing [[maximum matching]]s on graphs[[Graph (discrete mathematics)|graph]]s. The algorithm was developed by [[Jack Edmonds]] in 1961,<ref name = "glimpse">{{Citation
| last = Edmonds
| first = Jack
Line 17 ⟶ 19:
| year = 1965
| pages = 449–467
}}</ref> Given a general [[Graph (discrete mathematics)|graph]] {{math|1=''G'' = (''V'', ''E'')}}, the algorithm finds a matching ''{{mvar|M''}} such that each vertex in ''{{mvar|V''}} is incident with at most one edge in ''{{mvar|M''}} and {{math|{{abs|''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.
The algorithm runs in time <{{math>|[[Big O( notation|''O'']]({{abs|''E''}}{{abs||''V''}}{{sup|^2}})</math>}}, where <{{math>|E{{abs|</math>''E''}}}} is the number of [[edge (graph)|edges]] of the graph and <{{math>|{{abs|''V|</math>''}}}} is its number of [[vertex (graph)|vertices]]. A better running time of <math>O( |E| \sqrt{ |V|^{1/ 2} )</math> for the same task can be achieved with the much more complex algorithm of Micali and Vazirani.<ref name = "micali">{{cite conference
