Gabow's Cardinality Matching Algorithm in General Graphs: Implementation and Experiments
<|reference_start|>Gabow's Cardinality Matching Algorithm in General Graphs: Implementation and Experiments: It is known since 1975 (\cite{HK75}) that maximum cardinality matchings in bipartite graphs with $n$ nodes and $m$ edges can be computed in time $O(\sqrt{n} m)$. Asymptotically faster algorithms were found in the last decade and maximum cardinality bipartite matchings can now be computed in near-linear time~\cite{NearlyLinearTimeBipartiteMatching, AlmostLinearTimeMaxFlow,AlmostLinearTimeMinCostFlow}. For general graphs, the problem seems harder. Algorithms with running time $O(\sqrt{n} m)$ were given in~\cite{MV80,Vazirani94,Vazirani12,Vazirani20,Vazirani23,Goldberg-Karzanov,GT91,Gabow:GeneralMatching}. Mattingly and Ritchey~\cite{Mattingly-Ritchey} and Huang and Stein~\cite{Huang-Stein} discuss implementations of the Micali-Vazirani Algorithm. We describe an implementation of Gabow's algorithm~\cite{Gabow:GeneralMatching} in C++ based on LEDA~\cite{LEDAsystem,LEDAbook} and report on running time experiments. On worst-case graphs, the asymptotic improvement pays off dramatically. On random graphs, there is no improvement with respect to algorithms that have a worst-case running time of $O(n m)$. The performance seems to be near-linear. The implementation is available open-source.<|reference_end|>
@article{ansaripour2024gabow's,
    title={Gabow's Cardinality Matching Algorithm in General Graphs: Implementation
  and Experiments},
    author={Matin Ansaripour and Alireza Danaei and Kurt Mehlhorn},
    journal={arXiv preprint arXiv:2409.14849},
    year={2024},
    archivePrefix={arXiv},
    eprint={2409.14849},
    primaryClass={cs.DS}
}