The weighted matching approach to maximum cardinality matching
From MaRDI portal
(Redirected from Publication:4601124)
Abstract: Several papers have achieved time 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 .
Recommendations
Cited in
(10)- Weighted restricted 2-matching
- scientific article; zbMATH DE number 515942 (Why is no real title available?)
- Weighted matching as a generic pruning technique applied to optimization constraints
- A weighted approach to the maximum cardinality bipartite matching problem with applications in geometric settings
- Blocking trails for \(f\)-factors of multigraphs
- A weight-scaling algorithm for \(f\)-factors of multigraphs
- A formal analysis of capacity scaling algorithms for minimum cost flows
- Maximum flow and minimum-cost flow in almost-linear time
- Maximum cardinality \(f\)-matching in time \(O(n^{2/3}m)\)
- A query-efficient quantum algorithm for maximum matching on general graphs
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)
