2014/12/31 by Harold N. Gabow, Gabow, Harold N.
Computer Science · #Advanced Graph Theory Research #Algorithms and Data Compression #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #cs.DS #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1501.00212
arxiv created 2014/12/31 · openalex publication_date 2014/12/31 · arxiv updated 2015/01/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The algorithm of Micali and Vazirani \citeMV finds a maximum cardinality matching in time O(√ n m) if an efficient set-merging algorithm is used. The latter is provided by the incremental-tree set-merging algorithm of \citeGabTar. Details of this application to matching were omitted from \citeGabTar and are presented in this note.