Approximation Algorithms for Maximum Matchings in Geometric Intersection Graphs

Sariel Har-Peled, Everett Yang

We present a $(1-\epsilon )$-approximation algorithms for maximum cardinality matchings in disk intersection graphs -- all with near linear running time. We also present estimat…