Myth -- and grapevine -- has it that the Micali-Vazirani maximum
matching algorithm is "too complicated".
The purpose of this talk is to show the stunningly beautiful structure
of minimum length alternating paths
and to convince the audience that our algorithm exploits this
structure in such a simple and natural manner
that the entire algorithm can fit into one's mind as a single thought.
For all practical purposes, the Micali-Vazirani algorithm, discovered
in 1980, is still the most efficient
known algorithm (for very dense graphs, slight asymptotic improvement
can be obtained using fast
matrix multiplication). Yet, no more than a handful of people have
understood this algorithm; we hope
to change this.
Based on the following two papers: