Puissance de l'attente aux stations pour l'exploration des réseaux de transport public

David Ilcinkas (1, 2) , Ahmed Mouhamadou Wade (1, 2)

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

Nous étudions le problème de l'exploration, par une entité mobile, d'une classe de graphes dynamiques appelés graphes périodiquement variables (PV-graphes). Ils sont définis par un ensemble de transporteurs suivant infiniment leur route respective le long des stations du réseau, et modélisent donc naturellement les réseaux de transport public. Flocchini, Mans et Santoro [FMS09] ont étudié ce problème dans le cas où l'agent doit toujours rester sur les transporteurs. Dans ce papier, nous étudions 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 <= 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.

Mots clés: Exploration; Graphes dynamiques; Agent mobile; PV-graphes

Domaines: Algorithme et structure de données [cs.DS]; Calcul parallèle, distribué et partagé [cs.DC]

David Ilcinkas, Ahmed Mouhamadou Wade. Puissance de l'attente aux stations pour l'exploration des réseaux de transport public. 14èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications (AlgoTel), 2012, La Grande Motte, France. pp.107-110. ⟨hal-00691015⟩