Exploration de graphes anonymes avec des jumellesReport as inadecuate




Exploration de graphes anonymes avec des jumelles - Download this document for free, or read online. Document in PDF available to download.

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





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

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



DOWNLOAD PDF




Related documents