Approximation Algorithms for Maximum Matchings in Geometric Intersection Graphs

Sariel Har-Peled, Everett Yang

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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).

Original languageEnglish (US)
Title of host publication38th International Symposium on Computational Geometry, SoCG 2022
EditorsXavier Goaoc, Michael Kerber
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959772273
DOIs
StatePublished - Jun 1 2022
Externally publishedYes
Event38th International Symposium on Computational Geometry, SoCG 2022 - Berlin, Germany
Duration: Jun 7 2022Jun 10 2022

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume224
ISSN (Print)1868-8969

Conference

Conference38th International Symposium on Computational Geometry, SoCG 2022
Country/TerritoryGermany
CityBerlin
Period6/7/226/10/22

Keywords

  • Matchings
  • approximation algorithms
  • disk intersection graphs

ASJC Scopus subject areas

  • Software

Fingerprint

Dive into the research topics of 'Approximation Algorithms for Maximum Matchings in Geometric Intersection Graphs'. Together they form a unique fingerprint.

Cite this