论文标题
几何相交图中最大匹配的近似算法
Approximation Algorithms for Maximum Matchings in Geometric Intersection Graphs
论文作者
论文摘要
我们提出了$（1- \ varepsilon）$ - 在磁盘相交图中最大基数匹配的近似算法 - 所有这些都具有接近线性的运行时间。我们还提出了估计算法，该算法返回$（1 \ pm \ varepsilon）$ - 近似此类匹配项的近似 - 该算法在单位磁盘的线性时间内运行，而通用磁盘的$ O（N \ log n）$（只要密度相对小）即可。
We present a $(1- \varepsilon)$-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 \varepsilon)$-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).
