Quel est l'algorithme exact pour trouver la clique maximale d'un graphique de disque unitaire donné?

Question

Un graphique de disque d'unité est un graphique d'intersection $ g = (v, e) $, tel que compte tenu de disques $ n $ sur l'avion avec un rayon identique. Chaque disque $ d_u $ correspond à un sommet $ u dans v $, et il y a un bord $ uv dans e $ si, et seulement si $ d_u $ et $ d_v $ se croisent.

En 1990, Clark, Colbourn et Johnson ont montré que le problème peut être résolu en temps polynomial. Cependant, le papier lié ne fournit pas d'algorithme exact.

J'étudie le papier depuis un certain temps, et je ne vois toujours pas comment les observations de la section 3 peuvent être utilisées pour développer un algorithme. Surtout parce que les ensembles de points qui sont utilisés pour prouver que les affirmations sont infinies.

De plus, j'ai scanné à travers de nombreux articles, et tous mentionnent la solvabilité en temps polynomial uniquement. Je ne pouvais même trouver une définition verbale de l'algorithme nulle part.

Je ne demande pas de codage ou d'un algorithme bien défini, mais j'apprécierais vraiment un algorithme complet à peu près écrit.