The Weighted Matching Approach to Maximum Cardinality Matching

2017/03/11 by Gabow, Harold N. · 2 citations
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.1703.03998

Abstract

Several papers have achieved time O(√ 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(√ n m).

Cited by

• Forgetting Alternation and Blossoms: A New Framework for Fast Matching Augmentation and Its Applications to Sequential/Distributed/Streaming Computation
• Limitation of Quantum Walk Approach to the Maximum Matching Problem

Related

• A Weighted Approach to the Maximum Cardinality Bipartite Matching Problem with Applications in Geometric Settings
• Scaling algorithms for approximate and exact maximum weight matching
• A Proof of the MV Matching Algorithm
• A Nearly Linear-Time Distributed Algorithm for Maximum Cardinality Matching
• Fully dynamic 3/2 approximate maximum cardinality matching in O(√(n)) update time