Eleonora Guerrini (GREYC, Caen)

En 1998 Karposki et al. ont introduit les codes identifiants pour répondre à la question suivante. On dispose d’un réseau très grand de processeurs. Vu leur nombre, avoir un processeur défectueux est une situation fréquente. Comment savoir à coup sûr quel est ce processeur défectueux, et à moindre coût ?

Le bon contexte pour ce type de questions est la théorie des graphes. Un sommet mystère ( x ) se cache (peut-être) dans un graphe donné G. Pour savoir où il se cache, on a le droit d’interroger les sommets du graphe en leur demandant s’ils voient dans leur voisinage le sommet mystère. Un code identifiant est un sous-ensemble de sommets de G tel que l’on peut découvrir le sommet mystère (pour tout choix de x ). Si un tel code existe, le problème est en général de déterminer la cardinalité minimale. Le problème est NP-difficile en général, et il existe des algorithmes polynomiaux pour quelques classes de graphes, comme par exemple les arbres.

Dans cet exposé on présentera les problématiques des codes identifiants pour des classes de graphes connues, quelques problèmes ouverts, quelques variantes et des résultats d’existence dans les cas extrémaux.