Utiliser des jumelles pour explorer rapidement les graphes triangulésReport as inadecuate




Utiliser des jumelles pour explorer rapidement les graphes triangulés - Download this document for free, or read online. Document in PDF available to download.

1 LIF - Laboratoire d-informatique Fondamentale de Marseille

Résumé : Nous nous intéressons à l-exploration de graphes par un agent mobile. Il est connu que sans information - globale - sur le graphe taille, diamètre,

., un agent peut explorer et s-arrêter uniquement si le graphe est un arbre. Afin d-explorer plus de graphes avec arrêt sans information - globale - sur le graphe exploré, l-agent est équipé de jumelles lui permettant de voir le graphe induit par les sommets voisins du sommet courant. Avec des jumelles, il est possible d-explorer une très large famille maximale de graphes avec arrêt CGN15. Cependant, tout algorithme d-exploration universel pour cette famille a une complexité non calculable. Nous considérons donc dans cette étude une sous famille de ces graphes, les graphes de Weetman, qui sont une généralisation de la famille des graphes triangulés. Nous présentons un algorithme d-exploration pour cette famille ne nécessitant aucune information globale sur le graphe exploré. Cet algorithme est efficace dans le sens où même si les graphes de Weetman peuvent être très denses un nombre quadratique d-arêtes, le nombre de mouvements effectués par l-agent restera linéaire en le nombre de sommets. De plus, notre algorithme permet également de construire une carte du graphe.

Mots-clés : Agent mobile Exploration de graphes Graphes anonymes Revêtement Graphes Triangulés





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

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



DOWNLOAD PDF




Related documents