Complexité de l’exploration des graphes dynamiques T-intervalle-connexes

Ahmed Wade

Jeudi 02 octobre 2014 à 11h, salle 25-26/101

Slides

Dans cet exposé, je vais parler de l’étude des graphes dynamiques T-intervalle-connexes du point de vue du temps nécessaire à leur exploration par une entité mobile (agent). Un graphe dynamique est T-intervalle-connexe (T >= 1) si pour chaque fenêtre de T unités de temps, il existe un sous-graphe couvrant connexe stable. Cette propriété de stabilité de connexion au cours du temps a été introduite par Kuhn, Lynch et Oshman (STOC 2010).