Minimum clique partition in unit disk graphs (Q659693): Difference between revisions

The minimum clique partition is known to be an NP-hard problem. The paper presents two algorithms for finding approximate solutions of the clique partition of unit disk graphs. A unit disk graph corresponds to a set of points in the plane. Two vertices are adjacent if and only if the distance between corresponding points is at most \(1\). The first algorithm presented in the article is a polynomial approximation scheme that computes an \((1+\varepsilon)\)-approximation in \(n^{O(1/\varepsilon^2)}\) time. The second algorithm is a randomized version with approximation ratio \(2.16\) and \(O(n^2)\) running time.