Approximation algorithms for maximum matchings in undirected graphs

DOI10.1137/1.9781611975215.6MaRDI QIDQ6539156zbMATH OpenFDO

Authors Fanny Dufossé, Kamer Kaya, Ioannis Panagiotas, Bora Uçar

Publication date 14 May 2024

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

Mathematics Subject Classification ID

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

Recommendations

• New approximation results on graph matching and related problems
• scientific article; zbMATH DE number 177842
• Approximating matchings in parallel
• A simpler linear time \( \frac{2}{3} - \varepsilon\) approximation for maximum weight matching
• Linear-time approximation for maximum weight matching

Cited in

(1)

• New approximation results on graph matching and related problems

This page was built for publication: Approximation algorithms for maximum matchings in undirected graphs

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