Dispelling an Old Myth about an Ancient Algorithm

Опубликовано 28 июля 2016, 23:16

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: cc.gatech.edu/~vazirani/MV.pdf cc.gatech.edu/~vazirani/Theory...