The Weighted Matching Approach to Maximum Cardinality Matching
Harold N. Gabow · Fundamenta Informaticae · 2017
Several papers have achieved time Onm 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 ex tend this to a complete algorithm for maximum cardinality matching in time Onm.