A Simplification of the MV Matching Algorithm and its Proof

Vijay V. Vazirani

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.

Knowledge Graph

arrow_drop_up

Comments

Sign up or login to leave a comment