Efficient algorithms for variants of weighted matching and assignment problems

DOI10.1007/S11786-007-0028-0zbMATH Open1158.68034OpenAlexW2088839895MaRDI QIDQ942999FDOQ942999

Authors: Satyajit Banerjee, Atish Datta Chowdhury, Subhas Kumar Ghosh 

Publication date: 8 September 2008

Published in: Mathematics in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s11786-007-0028-0

Recommendations

• Efficient algorithms for maximum weight matchings in general graphs with small edge weights
• scientific article; zbMATH DE number 795216
• A weighted approach to the maximum cardinality bipartite matching problem with applications in geometric settings
• New algorithms for maximum weight matching and a decomposition theorem
• Efficient approximation algorithms for weighted \(b\)-matching

zbMATH Keywords

approximation algorithmgraph algorithmreductionmaximum weight maximum cardinality matching

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Nonnumerical algorithms (68W05) Approximation algorithms (68W25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cited In (6)

• Parameterized algorithms for weighted matching and packing problems
• Solving various weighted matching problems with constraints
• Short covering codes arising from matchings in weighted graphs
• A new class of heuristic algorithms for weighted perfect matching
• Weighted matching as a generic pruning technique applied to optimization constraints
• Short coverings and matching in weighted graphs

This page was built for publication: Efficient algorithms for variants of weighted matching and assignment problems

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