Edmonds' Blossom Algorithm

Jack Edmonds, 1965

Edmonds (1965) finds augmenting paths in non-bipartite graphs by contracting odd cycles (blossoms) into single vertices, augmenting, then expanding. This exhibit shows augmenting paths growing the matching and one blossom contraction.