The Weighted Matching Approach to Maximum Cardinality Matching

2017/08/09 by Harold N. Gabow · 1 citation
Computer Science · Mathematics · #Algorithms and Data Compression #Data Management and Algorithms #Bayesian Modeling and Causal Inference #Matching (statistics) #Cardinality (data modeling) #Mathematics #3-dimensional matching #Computer science #Algorithm #Combinatorics #Blossom algorithm #Data mining #Statistics

paper · doi:10.3233/fi-2017-1555

openalex publication_date 2017/08/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/30

Abstract

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.

Citations

• A linear-time algorithm for a special case of disjoint set union
• Faster scaling algorithms for general graph matching problems
• Combinatorial optimization: networks and matroids
• An n^5/2 Algorithm for Maximum Matchings in Bipartite Graphs

Cited by

• Hopcroft–Karp algorithm [wikipedia]

Related

• The Weighted Matching Approach to Maximum Cardinality Matching
• A Nearly Linear-Time Distributed Algorithm for Maximum Cardinality Matching
• A Proof of the MV Matching Algorithm
• A Weighted Approach to the Maximum Cardinality Bipartite Matching Problem with Applications in Geometric Settings
• Set-merging for the Matching Algorithm of Micali and Vazirani