Exploration des graphes dynamiques T-intervalle-connexes

Ahmed Mouhamadou Wade (1, 2)

1 CEPAGE - Algorithmics for computationally intensive applications over wide scale distributed platforms
2 Combinatoire et Algorithmique

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.

Mots clés: Graphes dynamiques; Agent mobile; T-intervalle-connexité; Exploration

Domaines: Complexité [cs.CC]; Algorithme et structure de données [cs.DS]; Robotique [cs.RO]; Combinatoire [math.CO]

Ahmed Mouhamadou Wade. Exploration des graphes dynamiques T-intervalle-connexes. CNRIA 2013 - 5ème Colloque National sur la Recherche en Informatique et ses Applications, May 2013, Zinguichor, Sénégal. pp.78-85. ⟨hal-00965933⟩