Séminaire

Possibilité de visio-conférence @IP : 193.55.95.10 Nom du correspondant technique : Nicolas CHAMPEIL Tél correspondant technique : 04 73 40 50 15 / 06 78 34 55 26 Mail : nicolas.champeil@isima.fr Tél salle de visio : 04 73 40 50 47 Nous présenterons quelques résultats récents dans le domaine des problèmes d’identification dans les graphes, en particulier le problème des ensembles dominants-localisateurs et celui des bases métriques. Ces problèmes consistent à trouver un (petit) ensemble de sommets du graphe tel que tous les sommets restants sont distingués (soit par leur voisinage dans l’ensemble sélectionné, soit par leurs distances aux sommets de cet ensemble). Cela correspond à des situations dans lesquelles on souhaite localiser certains éléments d’un réseau (feux dans un bâtiment, ordinateurs défectueux, etc). Nous discuterons la taille d’une solution optimale à ces problèmes par rapport à l’ordre du graphe, ainsi que leur complexité algorithmique pour diverses classes de graphes. Les résultats présentés sont issus de collaborations avec George Mertzios, Reza Naserasr, Aline Parreau, Petru Valicov ainsi que Michael Henning, Christian Löwenstein, Thomas Sasse.