The Weighted Matching Approach to Maximum Cardinality Matching

Abstract

Several papers have achieved time $O(\sqrt{n}m)$ for cardinality matching, starting from first principles. This results in a long derivation. We simplify the task by employing well-known concepts for maximum weight matching. We use Edmonds' algorithm to derive the structure of shortest augmenting paths. We extend this to a complete algorithm for maximum cardinality matching in time $O(\sqrt{n}m)$.

18 pages