Blossom Algorithm

The blossom algorithm is a graph theory algorithm for constructing maximum matchings on graphs, developed by Jack Edmonds in 1961 and published in 1965. Given a general graph, the algorithm finds a matching in which each vertex is incident with at most one matched edge and the number of matched edges is maximized, built by iteratively improving an initial empty matching along augmenting paths; unlike bipartite matching, its key new idea is that an odd length cycle in the graph, called a blossom, is contracted to a single vertex, with the search continuing iteratively in the contracted graph. It is considered important because it gave the first proof that a maximum size matching could be found using a polynomial amount of computation time.