From LaBRI - Laboratoire Bordelais de Recherche en Informatique

Theses: 2013Casteigt

Classification automatique de graphes dynamiques

Étant donné un graphe dynamique, donné sous la forme d'une séquence de graphes statiques ou bien comme une succession d'évènements topologiques (apparitions/disparitions de liens de communication), on s'intéresse à tester automatiquement certaines propriétés temporelles sur le graphe. Les propriétés qui nous intéressent correspondent à des conditions nécessaires et/ou suffisantes pour la réalisation de tâches distribuées classiques (élection, diffusion, comptage, etc.) Nous avons répertorié à ce jour une vingtaine de propriétés. Par exemple, le réseau est-il temporellement connexe ? (existence d'un {\it trajet}, {\it i.e.} d'une succession d'arêtes dont les dates d'existence sont temporellement croissantes, depuis chaque sommet vers chaque autre sommet); certaines arêtes réapparaissent-elles dans un temps borné ou de manière périodique ? À noter que la dimension temporelle introduit ici son propre niveau d'orientation, indépendant de celui des arêtes. Être capable de vérifier ce type de propriété automatiquement nous permettrait de déterminer dans un contexte de mobilité donné (p. ex. drones, robots, voitures, dont on peut obtenir ou générer des traces de connexité), les tâches réalisables par l'ensemble des entités.

Récupéré sur http://www.labri.fr/index.php?n=Theses.2013Casteigt
Page mise à jour le 27/05/2013 à 09:22