An Improved Definition of Blossoms and a Simpler Proof of the MV Matching Algorithm
Vijay V. Vazirani · 2012
For all practical purposes, the Micali-Vazirani general graph maximum matching algorithm is still the most efficient known algorithm for the problem. The purpose of this paper is to provide a complete proof of correctness of the algorithm in the simplest possible terms; graph-theoretic machinery developed for this purpose also helps simplify the algorithm.