Gabow's $O(\sqrt{n}m)$ Maximum Cardinality Matching Algorithm, Revisited

Kurt Mehlhorn, Romina Nobahari

We revisit Gabow's $O(\sqrt{n}m)$ maximum cardinality matching algorithm (The Weighted Matching Approach to Maximum Cardinality Matching, Fundamenta Informaticae, 2017). It adapts…