b'@online{Ansaripour2409.14849,'b"\nTITLE = {Gabow's Cardinality Matching Algorithm in General Graphs: Implementation and Experiments},\nAUTHOR = {Ansaripour, Matin and Danaei, Alireza and Mehlhorn, Kurt},\nLANGUAGE = {eng},\nURL = {https://arxiv.org/abs/2409.14849},\nEPRINT = {2409.14849},\nEPRINTTYPE = {arXiv},\nYEAR = {2024},\nMARGINALMARK = {$\\bullet$},\nABSTRACT = {It is known since 1975 (\\cite{HK75}) that maximum cardinality matchings in<br>bipartite graphs with $n$ nodes and $m$ edges can be computed in time<br>$O(\\sqrt{n} m)$. Asymptotically faster algorithms were found in the last decade<br>and maximum cardinality bipartite matchings can now be computed in near-linear<br>time~\\cite{NearlyLinearTimeBipartiteMatching,<br>AlmostLinearTimeMaxFlow,AlmostLinearTimeMinCostFlow}. For general graphs, the<br>problem seems harder. Algorithms with running time $O(\\sqrt{n} m)$ were given<br>in~\\cite{MV80,Vazirani94,Vazirani12,Vazirani20,Vazirani23,Goldberg-Karzanov,GT91,Gabow:GeneralMatching}.<br>Mattingly and Ritchey~\\cite{Mattingly-Ritchey} and Huang and<br>Stein~\\cite{Huang-Stein} discuss implementations of the Micali-Vazirani<br>Algorithm. We describe an implementation of Gabow's<br>algorithm~\\cite{Gabow:GeneralMatching} in C++ based on<br>LEDA~\\cite{LEDAsystem,LEDAbook} and report on running time experiments. On<br>worst-case graphs, the asymptotic improvement pays off dramatically. On random<br>graphs, there is no improvement with respect to algorithms that have a<br>worst-case running time of $O(n m)$. The performance seems to be near-linear.<br>The implementation is available open-source.<br>},\n}\n"