The weighted matching approach to maximum cardinality matching

DOI10.3233/FI-2017-1555zbMATH Open1387.68316arXiv1703.03998MaRDI QIDQ4601124FDOQ4601124

Authors: Harold N. Gabow 

Publication date: 19 January 2018

Published in: Fundamenta Informaticae (Search for Journal in Brave)

Abstract: Several papers have achieved time $O(sqrtnm)$ 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(sqrtnm)$.

Full work available at URL: https://arxiv.org/abs/1703.03998

Recommendations

• Linear-time approximation for maximum weight matching
• scientific article; zbMATH DE number 177842
• Efficient algorithms for finding maximum matching in graphs
• scientific article; zbMATH DE number 515942
• scientific article; zbMATH DE number 3902700

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms (68W40) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cited In (7)

• Title not available (Why is that?)
• A weight-scaling algorithm for \(f\)-factors of multigraphs
• Blocking trails for \(f\)-factors of multigraphs
• Weighted restricted 2-matching
• Title not available (Why is that?)
• A query-efficient quantum algorithm for maximum matching on general graphs
• Weighted matching as a generic pruning technique applied to optimization constraints

This page was built for publication: The weighted matching approach to maximum cardinality matching

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4601124)