Codes identifiants dans les graphes

La notion de code identifiant a été introduite par Karpovsky et al. en 1998 afin de modéliser les problèmes de détection et localisation de pannes dans les réseaux multi-processeurs. On peut imaginer un code identifiant comme un ensemble de capteurs placés sur un graphe permettant de détecter et localiser un intrus se cachant sur un sommet, l’idée étant de placer le moins de capteurs possibles pour réaliser cette tâche.Plus précisément, un code identifiant C dans un graphe non-orienté est un ensemble couvrant (dominating set) qui permet de plus l’identification des sommets par la trace de leur voisinage sur C. Cette notion se généralise afin de permettre l’identification d’ensembles d’au plus k sommets à une distance r.Nous présenterons les codes identifiants ainsi des résultats s’y rapportant (taille minimale, maximale, complexité algorithmique), ainsi que quelques notions connexes, comme la classe des graphes sans-jumeaux, qui sont les graphes admettant des codes identifiants.