Evènement pour le groupe GT Graphes et Applications


Date 2014-07-04  14:00-15:00
TitreCodes séparateurs et surveillance de trafic 
RésuméCette présentation porte sur les problèmes de séparation dont un exemple bien étudié au Labri est celui de code identifiant dans un graphe. Dans le cas général, il s'agit de trouver un ensemble de propriétés aussi petit que possible permettant de distinguer un ensemble d'individus donné. Nous étudierons des modèles basés sur différentes structures combinatoires et comparerons leur expressivité. Nous nous intéresserons ensuite au problème de surveillance de trafic dans un réseau qui consiste à déterminer où placer des capteurs sur les arcs d'un graphe pour pouvoir reconstituer le chemin suivi par un marcheur. Nous exprimerons ce problème comme un problème de séparation en introduisant un nouveau modèle : la séparation sur un langage. Nous étudierons ensuite ce nouveau problème et développerons des algorithmes de résolution, particulièrement sur les instances spécifiques issues du problème de surveillance de trafic. 
LieuSalle 178 
OrateurThomas Bellitto 



Aucun document lié à cet événement.

Retour
Retour à l'index