Complexité du problème de l'unicité d'un transversal minimum dans un graphe

Olivier Hudry (1, 2, 3) , Antoine Lobstein (4)

1 IP Paris - Institut Polytechnique de Paris
2 INFRES - Département Informatique et Réseaux
3 C2 - Cybersécurité et Cryptographie
4 LRI - Laboratoire de Recherche en Informatique

Complexité du problème de l'unicité d'un transversal minimum dans un graphe

Keywords: théorie de la complexité; problèmes NP; difficiles; optimisation combinatoire; théorie des graphes; transversal; clique; stable; problème de satisfiabilité (SAT); transformations polynomiales

Domains: Operations Research [math.OC]; Combinatorics [math.CO]

Olivier Hudry, Antoine Lobstein. Complexité du problème de l'unicité d'un transversal minimum dans un graphe. 23ème congrès annuel de la Société Française de Recherche Opérationnelle et d'Aide à la Décision, INSA Lyon, Feb 2022, Villeurbanne - Lyon, France. ⟨hal-03596176⟩