Complexité de l'exploration par agent mobile des graphes dynamiques

Abstract

Cette thèse porte sur l’étude de la complexité de l’exploration de graphes dynamiquespar agent mobile. Une entité mobile (appelée agent) se déplaçant dans un graphe dynamiquedoit traverser/visiter au moins une fois chacun de ses sommets. (Le tempsde traversée d’une arête est unitaire.) Ce problème fondamental en algorithmique paragents mobiles a été très étudié dans les graphes statiques depuis l’article originel deClaude Shannon. Concernant les graphes dynamiques, seul le cas des graphes dynamiquespériodiques a été étudié. Nous étudions ce problème dans deux familles degraphes dynamiques, les graphes dynamiques périodiquement variables (PV-graphes)et les graphes dynamiques T-intervalle-connexes. Les résultats obtenus dans cette thèseaméliorent des résultats existants et donnent des bornes optimales sur le problèmeétudié.