Séminaire

Dans le cadre du problème du Traffic Monitoring, on modélise un réseau par un graphe orienté et on a la possibilité de munir de capteurs les arcs de ce graphe. Lorsqu’un objet circule dans le réseau, il active un capteur à chaque fois qu’il passe par un arc équipé et la séquence ordonnée des capteurs qu’il a activés constitue ce que l’on appelle la signature de la marche de l’objet. Les données du problème sont un graphe orienté (éventuellement pondéré) et un ensemble de marches sur le graphe que l’objet peut prendre. L’objectif est de chercher le plus petit ensemble d’arcs (ou le moins coûteux) à munir de capteurs tel que toutes les marches possibles aient des signatures différentes et qu’on soit ainsi capable de reconstituer exactement la trajectoire de l’objet à partir des informations envoyées par les capteurs. L’étude de ce problème nous amènera à étudier dans un premier temps la notion proche de code séparateur et à développer des modèles plus puissants. Le problème de Traffic Monitoring étant NP-complet en la taille de l’ensemble des marches à distinguer (qui peut être infini), il est exclu de le résoudre dans le cas général mais nous nous demanderons quels ensembles de marches peuvent avoir un intérêt pratique et chercherons des propriétés de ces ensembles qui nous permettront de mettre au point des algorithmes plus efficaces. Ces considérations nous conduiront notamment à étudier les graphes à transitions interdites qui sont particulièrement pratiques pour modéliser les réseaux routiers.