Approximation Algorithms for Maximum Matchings in Geometric Intersection Graphs

01/05/2022

∙

by   Sariel Har-Peled, et al.

∙

0

∙

share

We present a (1- ε)-approximation algorithms for maximum cardinality matchings in disk intersection graphs – all with near linear running time. We also present estimation algorithm that returns (1±ε)-approximation to the size of such matchings – this algorithms run in linear time for unit disks, and O(n log n) for general disks (as long as the density is relatively small).