Blossom algorithm

An algorithm for finding maximum matchings in general graphs that contracts odd cycles, called blossoms, while searching for augmenting paths.

Matching (graph theory): A set of graph edges that share no endpoints. The algorithm enlarges a matching until no larger one exists.
Berge's lemma: A theorem stating that a matching is maximum exactly when no augmenting path exists. It supplies the stopping condition for the algorithm.
Jack Edmonds: A mathematician and computer scientist whose work shaped combinatorial optimization and polyhedral theory. Edmonds introduced the blossom method for general-graph matching.
Maximum matching: A matching containing the largest possible number of edges in a graph. The algorithm computes this optimum even when the graph is not bipartite.
Hopcroft–Karp algorithm: An algorithm that finds maximum matchings in bipartite graphs using layered augmenting paths. It is faster for bipartite graphs, where odd-cycle blossoms cannot occur.
Augmenting path: A path whose edges alternate between unmatched and matched edges, beginning and ending with unmatched edges. Flipping matched status along this path increases the matching by one edge.
Symmetric difference: The set of elements belonging to exactly one of two sets. The symmetric difference of two matchings decomposes into paths and cycles that explain augmentation.
Paths, Trees, and Flowers: A 1965 paper by Jack Edmonds presenting an efficient algorithm for matching in general graphs. This paper introduced the contraction idea behind the algorithm.
Perfect matching: A matching that covers every vertex of a graph. A perfect matching exists precisely when a maximum matching covers all vertices.
Hungarian algorithm: An algorithm for solving the assignment problem in a weighted bipartite graph. It exploits bipartite assignment structure rather than contracting odd cycles.

Linked from 2 pages

Tutte's theorem on perfect matchingsRelated: It handles odd-cycle structure that bipartite matching methods cannot directly resolve.