Seminar, Hosted by Simons Institute for the Theory of Computing, UC Berkeley
A Theory of Alternating Paths and Blossoms, from the Perspective of Minimum Length
University of California, Irvine
Abstract
Vijay V. Vazirani presents a two-part account of the Micali–Vazirani algorithm for maximum-cardinality matching. The first part develops background from bipartite matching and Edmonds’ algorithm, explains why shortest augmenting paths create difficulties, and introduces double depth-first search. The second develops a structural theory of alternating paths and blossoms that supports the algorithm and its recently completed proof.
Topics
- Micali–Vazirani algorithm, search World Wide
- maximum-cardinality matching, search World Wide
- bipartite matching, search World Wide
- Edmonds’ algorithm, search World Wide
- shortest augmenting paths, search World Wide
- double depth-first search, search World Wide
- alternating paths, search World Wide
- blossoms, search World Wide
- augmenting paths, search World Wide