Approximation Algorithms for Maximum Matchings in Geometric Intersection Graphs

Abstract

We present a $(1-\epsilon )$-approximation algorithms for maximum cardinality matchings in disk intersection graphs -- all with near linear running time. We also present estimation algorithm that returns $(1\pm \epsilon )$-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).