Codes identifiants dans les graphes
ENS (amphithéâtre Galois sous la bibliothèque de mathématique)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 […]