@inproceedings{748dc7b351184e56a2d8caf43db197a6,
title = "Approximation Algorithms for Maximum Matchings in Geometric Intersection Graphs",
abstract = "We present a (1-e)-approximation algorithms for maximum cardinality matchings in disk intersection graphs - all with near linear running time. We also present an estimation algorithm that returns (1 ± e)-approximation to the size of such matchings - this algorithm runs in linear time for unit disks, and O(n log n) for general disks (as long as the density is relatively small).",
keywords = "Matchings, approximation algorithms, disk intersection graphs",
author = "Sariel Har-Peled and Everett Yang",
note = "Publisher Copyright: {\textcopyright} Sariel Har-Peled and Everett Yang; licensed under Creative Commons License CC-BY 4.0; 38th International Symposium on Computational Geometry, SoCG 2022 ; Conference date: 07-06-2022 Through 10-06-2022",
year = "2022",
month = jun,
day = "1",
doi = "10.4230/LIPIcs.SoCG.2022.47",
language = "English (US)",
series = "Leibniz International Proceedings in Informatics, LIPIcs",
publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",
editor = "Xavier Goaoc and Michael Kerber",
booktitle = "38th International Symposium on Computational Geometry, SoCG 2022",
}