The weighted matching approach to maximum cardinality matching

DOI10.3233/FI-2017-1555MaRDI QIDQ4601124zbMATH OpenFDO

Authors Harold N. Gabow

Publication date 19 January 2018

Published in Fundamenta Informaticae (Search for Journal in Brave)

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

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)

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)$.

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

Cited in

(7)

• A query-efficient quantum algorithm for maximum matching on general graphs
• Weighted matching as a generic pruning technique applied to optimization constraints
• scientific article; zbMATH DE number 7559248 (Why is no real title available?)
• Weighted restricted 2-matching
• scientific article; zbMATH DE number 515942 (Why is no real title available?)
• A weight-scaling algorithm for \(f\)-factors of multigraphs
• Blocking trails for \(f\)-factors of multigraphs

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)