Exploration des graphes dynamiques $T$-intervalle-connexes : le cas de l'anneau

Abstract

Dans cet article, nous étudions les 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). Nous nous concentrons sur le cas où le graphe sous-jacent est un anneau de taille n et nous montrons que la complexité en temps en pire cas est de 2n-T-Theta(1) unités de temps si l'agent connaît la dynamique du graphe, et n+ n/max{1,T-1} (delta-1) +- Theta(delta) unités de temps sinon, où delta est le temps maximum entre deux apparitions successives d'une arête.