Exploration des graphes dynamiques T-intervalle-connexes

Abstract

Dans cet article, nous étudions le problème d'exploration, par une entité mobile (agent), des graphes dynamiques T-intervalle-connexes qui ont comme graphe sous-jacent un anneau de taille $n$. Un graphe dynamique est T-intervalle-connexe ($T \geq 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 graphes dynamiques a été introduite par Kuhn, Lynch et Oshman~\cite{KLO10} (STOC 2010). Nous montrons que la complexité au pire cas est de $2n-T-\Theta(1)$ unités de temps si l'agent connaît la dynamique du graphe, et $\frac{n}{\max\{1, T-1\} } (\delta-1) +n \pm \Theta(\delta)$ unités de temps sinon, où $\delta$ est le temps maximum entre deux apparitions successives d'une arête.