The Blossom Shrinking Algorithm for Matching (OPTIMIZATION group meeting)

of the edges of $G$ such that no two edges in $M$ have a
vertex in common. I will present the basic algorithm for
computing a maximum matching in nonbipartite graphs due to Edmonds.
This algorithm is called the {\em blossom shrinking algorithm}
and serves as a basis for algorithms to compute matchings of
maximum weight or minimum weight perfect matchings.