Item

Abstract

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.