A Simplification of the MV Matching Algorithm and its Proof
Michael Huang, Clifford Stein · arXiv (Cornell University) · 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.