2026-07-21T19:26:05Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:7614 2024-03-06T10:39:48Z ddc:004 open_access

Extending Search Phases in the Micali-Vazirani Algorithm Huang, Michael Stein, Clifford matching graph algorithm experimental evaluation non-bipartite The Micali-Vazirani algorithm is an augmenting path algorithm that offers the best theoretical runtime of O(n^{0.5} m) for solving the maximum cardinality matching problem for non-bipartite graphs. This paper builds upon the algorithm by focusing on the bottleneck caused by its search phase structure and proposes a new implementation that improves efficiency by extending the search phases in order to find more augmenting paths. Experiments on different types of randomly generated and real world graphs demonstrate this new implementation's effectiveness and limitations. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Michael Huang and Clifford Stein 2017 Is Part Of LIPIcs, Volume 75, 16th International Symposium on Experimental Algorithms (SEA 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SEA.2017.10 urn:nbn:de:0030-drops-76141 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2017.10 eng https://creativecommons.org/licenses/by/3.0/legalcode