A parallel 2/3-approximation algorithm for vertex-weighted matching

DOI10.1137/1.9781611976229.2MaRDI QIDQ6539998zbMATH OpenFDO

Authors Ahmed Al-Herz, Alex Pothen

Publication date 15 May 2024

Full work available at URL https://doi.org/10.1137/1.9781611976229.2

Mathematics Subject Classification ID

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

Recommendations

• A \(2/3\)-approximation algorithm for vertex-weighted matching
• A 2/3-approximation algorithm for vertex weighted matching in bipartite graphs
• scientific article; zbMATH DE number 1759463
• Efficient approximation algorithms for weighted b-matching
• Parallel approximation algorithms for maximum weighted matching in general graphs

This page was built for publication: A parallel 2/3-approximation algorithm for vertex-weighted matching

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