 |
Complexité du problème de l'unicité d'un transversal minimum dans un graphe
1 : Télécom Paris
Télécom Paris, Télécom-Paris
2 : Télécom Paris
Télécom Paris, Télécom Paris
On étudie la complexité de l'unicité d'un transversal minimum dans un graphe. On montre que ce problème est au moins aussi difficile que le problème U-SAT consistant à savoir si une formule logique admet une unique solution. Puis on étend ce résultat à l'étude de l'unicité d'une clique maximum ou d'un stable maximum dans un graphe.
