Gabow's Cardinality Matching Algorithm in General Graphs: Implementation and Experiments

Matin Ansaripour, Alireza Danaei, Kurt Mehlhorn

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 fas…