Qual è l'algoritmo esatto per trovare la clique massima di un determinato grafico del disco unitario?
-
04-11-2019 - |
Domanda
Un grafico del disco unitario è un grafico di intersezione $ g = (v, e) $, tale che dati $ n $ dischi sul piano con raggio identico. Ogni disco $ d_u $ corrisponde a un vertice $ u in v $, e c'è un vantaggio $ uv in e $ se, e solo se $ d_u $ e $ d_v $ si interseca.
Nel 1990, Clark, Colbourn e Johnson ha mostrato che il problema può essere risolto nel tempo polinomiale. Tuttavia, la carta collegata non fornisce un algoritmo esatto.
Studio il documento da un po 'di tempo e ancora non vedo come le osservazioni nella Sezione 3 possano essere utilizzate per sviluppare un algoritmo. Soprattutto perché i set di punti che vengono utilizzati per dimostrare che le affermazioni sono infinite.
Inoltre, ho scansionato molti documenti e tutti menzionano solo la solvibilità del tempo polinomiale. Non riuscivo nemmeno a trovare una definizione verbale dell'algoritmo ovunque.
Non sto chiedendo una codifica o un algoritmo ben definito, ma apprezzerei davvero un algoritmo completo approssimativamente scritto.
Nessuna soluzione corretta