Exploration de graphes anonymes avec des jumellesReportar como inadecuado




Exploration de graphes anonymes avec des jumelles - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

1 LIF - Laboratoire d-informatique Fondamentale de Marseille 2 CNRS - Centre National de la Recherche Scientifique

Résumé : Nous nous intéressons à l-exploration de graphes par un agent mobile. Il est connu que sans information - globale - sur le graphe, un agent peut explorer et s-arrêter uniquement si le graphe est un arbre. C-est pourquoi nous équipons l-agent de - jumelles - lui permettant de voir le graphe induit par les sommets voisins du sommet courant. Dans cette étude, nous montrons que cette information locale donnée par les jumelles permet à l-agent d-explorer avec arrêt une plus large famille de graphes que les arbres. Nous prouvons la condition nécessaire suivante : un graphe est explorable seulement si son complexe de clique admet un revêtement universel fini. Puis, nous proposons un algorithme d-exploration universel pour tout graphe satisfaisant cette condition, prouvant ainsi que cette famille, appelée FC, est maximum pour l-exploration avec arrêt. Pour finir, nous montrons qu-il n-existe pas de fonction calculable pouvant borner la complexité de tout algorithme d-exploration de FC.

Mots-clés : Agent mobile exploration de graphes Graphes anonymes Revêtement Universel Simplement Connexe





Autor: Jérémie Chalopin - Emmanuel Godard - Antoine Naudin -

Fuente: https://hal.archives-ouvertes.fr/



DESCARGAR PDF




Documentos relacionados