A Proof of the MV Matching Algorithm

arXiv2012.03582MaRDI QIDQ6355451FDOQ6355451

Authors: Vijay V. Vazirani 

Publication date: 7 December 2020

Abstract: The Micali-Vazirani (MV) algorithm for maximum cardinality matching in general graphs, which was published in 1980 cite{MV}, remains to this day the most efficient known algorithm for the problem. This paper gives the first complete and correct proof of this algorithm. Central to our proof are some purely graph-theoretic facts, capturing properties of minimum length alternating paths; these may be of independent interest. An attempt is made to render the algorithm easier to comprehend.

This page was built for publication: A Proof of the MV Matching Algorithm

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6355451)