What is the exact algorithm to find maximum clique of a given unit disk graph?
-
04-11-2019 - |
Pregunta
A unit disk graph is an intersection graph $G = (V,E)$, such that given $n$ disks on the plane with identical radius. Each disk $d_u$ corresponds to a vertex $u \in V$, and there is an edge $uv \in E$ if, and only if $d_u$ and $d_v$ intersects.
In 1990, Clark, Colbourn, and Johnson showed that the problem can be solved in polynomial time. However, the linked paper does not provide an exact algorithm.
I have been studying the paper for some time, and I still don't see how the observations in Section 3 can be utilized to develop an algorithm. Mostly because point sets that are used to prove the claims are infinite.
Moreover, I have scanned through many papers, and all of them mention the polynomial-time solvability only. I could not even find a verbal definition of the algorithm anywhere.
I am not asking for coding or some well-defined algorithm, but I would really appreciate a roughly written complete algorithm.
No hay solución correcta