Élise Vandomme, Université du Québec à Montréal

Problèmes de couverture dans les graphes : les codes identifiants et leurs relaxations continues.

Les codes identifiants ont été introduits par Karpovsky, Chakrabarty et Levitin en 1998 pour modéliser un problème de détection de défaillance dans des réseaux multiprocesseurs. Un code identifiant est un ensemble dominant de sommets tel que le voisinage fermé de chaque sommet intersecté avec l'ensemble est unique. Le problème de trouver un code identifiant a largement été étudié. Cependant, sa formulation en termes de programmation linéaire en nombres entier a rarement été considérée. Dans cet exposé, nous comparerons le problème en nombres entiers avec sa relaxation continue et nous nous concentrerons sur le cas particulier des graphes sommets-transitifs.