Retour à l'index du GREYC

Séminaire Algorithmique

Site du CNRS

Séminaire Algorithmique

Le séminaire a lieu le mardi à 11 h 45 (sauf modification exceptionnelle), au campus Côte de Nacre, bâtiment Sciences 3, salle S3 351, 3ème étage.

Résumé du séminaire du Mardi 26 Octobre 2010

Détecter des défaillances dans les réseaux : un jeu de graphes

par 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.

GREYC
Campus Côte de Nacre, boulevard du Maréchal Juin
BP 5186
14032 Caen Cedex
FAX : +33 (0)2 31 56 73 30
http://www.greyc.fr