DROPS

Document

DOI: 10.4230/LIPIcs.SoCG.2022.47

Approximation Algorithms for Maximum Matchings in Geometric Intersection Graphs

Authors: Sariel Har-Peled and Everett Yang

Published in: LIPIcs, Volume 224, 38th International Symposium on Computational Geometry (SoCG 2022)

Abstract

We present a (1-ε)-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±ε)-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).

Cite as

Sariel Har-Peled and Everett Yang. Approximation Algorithms for Maximum Matchings in Geometric Intersection Graphs. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 47:1-47:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{harpeled_et_al:LIPIcs.SoCG.2022.47,
  author =	{Har-Peled, Sariel and Yang, Everett},
  title =	{{Approximation Algorithms for Maximum Matchings in Geometric Intersection Graphs}},
  booktitle =	{38th International Symposium on Computational Geometry (SoCG 2022)},
  pages =	{47:1--47:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-227-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{224},
  editor =	{Goaoc, Xavier and Kerber, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2022.47},
  URN =		{urn:nbn:de:0030-drops-160555},
  doi =		{10.4230/LIPIcs.SoCG.2022.47},
  annote =	{Keywords: Matchings, disk intersection graphs, approximation algorithms}
}

Search Results

Documents authored by Yang, Everett

Approximation Algorithms for Maximum Matchings in Geometric Intersection Graphs

Abstract

Cite as

Thanks for your feedback!

Could not send message