Home Bookmarks Papers Blog

# Approximation Algorithms for Maximum Matchings in Geometric Intersection Graphs

Sariel Har-Peled, and Everett Yang.
We present a $(1- \eps)$-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\pm \eps)$-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).
PDF. : arXiv.