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 dynamiques par agent mobile. Une entité mobile (appelée agent) se déplaçant dans un graphe dynamique doit traverser/visiter au moins une fois chacun de ses sommets. (Le temps de traversée d'une arête est unitaire.) Ce problème fondamental en algorithmique par agents mobiles a été très étudié dans les graphes statiques depuis l'article originel de Claude Shannon. Concernant les graphes dynamiques, seul le cas des graphes dynamiques périodiques a été étudié. Nous étudions ce problème dans deux familles de graphes dynamiques, les graphes dynamiques périodiquement variables (PV-graphes) et les graphes dynamiques T-intervalle-connexes. Les résultats obtenus dans cette thèse améliorent des résultats existants et donnent des bornes optimales sur le problème étudié. Un PV-graphe est défini par un ensemble de transporteurs suivant infiniment leur route respective le long des stations du réseau. En 2013, Flocchini, Mans et Santoro ont étudié le problème de l'exploration des PV-graphes en considérant que l'agent doit toujours rester sur les transporteurs. Cette thèse montre l'impact de la capacité d'attendre sur les stations. Nous prouvons que l'attente sur les stations permet à l'agent d'atteindre de meilleures complexités en pire cas : le nombre de mouvements est réduit d'un facteur multiplicatif d'au moins $\Theta(p)$, et la complexité en temps passe de $\Theta(kp^2)$ à $\Theta(np)$, où $n$ est le nombre de stations, $k$ le nombre de transporteurs, et $p$ la période maximale ($n\leq kp$ dans tout PV-graphe connexe). Par ailleurs, l'algorithme que nous proposons pour prouver les bornes supérieures permet de réaliser la cartographie du PV-graphe, en plus de l'explorer. Dans la deuxième partie de cette thèse, nous considérons le même problème (l'exploration) dans les graphes dynamiques T-intervalle-connexes. 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. Nous considérons dans un premier temps les graphes dynamiques T-intervalle-connexes qui ont un anneau de taille $n$ comme graphe sous-jacent et nous montrons que la complexité en temps en pire cas de leurs exploration est de $2n-T-\Theta(1)$ unités de temps si l'agent connaît la dynamique du graphe, et $n+ \frac{n}{\max\{1,T-1\}} (\delta-1) \pm\Theta(\delta)$ unités de temps sinon, où $\delta$ est le temps maximum entre deux apparitions successives d'une arête. Nous généralisons ensuite ces résultats en considérant une autre famille de graphes sous-jacents, les cactus à $n$ sommets. Un cactus est un graphe connexe dans lequel deux cycles ont au plus un sommet en commun. Nous donnons un algorithme qui permet d'explorer ces graphes dynamiques en au plus $2^{O(\sqrt{log n})} n$ unités de temps, et nous montrons que la borne inférieure de notre algorithme est $2^{\Omega(\sqrt{log n})} n$.