Efficient algorithms for variants of weighted matching and assignment problems

DOI10.1007/S11786-007-0028-0MaRDI QIDQ942999zbMATH OpenOpenAlexFDO

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

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)

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

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)