Evènement pour le groupe Algorithmique Distribuée


Date 2013-05-27  14:00-15:00
TitreExploration des graphes dynamiques T-intervalle-connexes : le cas de l'anneau 
RésuméDans cet exposé, je vais parler de l'étude des 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 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 connexion au cours du temps a été introduite par Kuhn, Lynch et Oshman~cite{KLO10} (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+ 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.  
LieuSalle 178 
OrateurWade Ahmed (Labri) 
UrlLabri 



Aucun document lié à cet événement.

Retour
Retour à l'index