[inria-00475863, v1] Comment battre la marche aléatoire en comptant ?

[inria-00475863, v1] Comment battre la marche aléatoire en comptant ?

-

Documents
4 pages
Lire
Le téléchargement nécessite un accès à la bibliothèque YouScribe
Tout savoir sur nos offres

Description

Author manuscript, published in "12èmes Rencontres Francophones sur les Aspects Algorithmiques de Télécommunications(AlgoTel) (2010)"†Comment battre la marche aleatoire´ en comptant ?1 1 2 3N. Hanusse and D. Ilcinkas and A. Kosowski and N. Nisse1 CNRS,LaBRI/INRIA,Universite´ deBordeaux1,Bordeaux,France,2Dept.ofAlg.andSyst.Modeling,Gdansk´ UniversityofTechnology,Gdansk,´ Poland,3 MASCOTTE,INRIA,I3S(CNRS/UNS),SophiaAntipolis,FranceNous etudions´ le probleme` consistant a` trouver une destination t dans un reseau,´ non fiable, graceˆ a` un agent mobile.Chaque nœud du reseau´ peut donner un conseil quant au prochain sommet a` visiter pour se rapprocher de t. Malheu-reusement, k nœuds, appeles´ menteurs, donnent de mauvais conseils. Il est connu que pour un graphe G de n sommetset de degre´ maximumD 3, atteindre une cible a` distance d de la position initiale peut demander un temps moyenW(minfd;kg)de 2 , pour tout d;k =O(logn), memeˆ lorsque G est un arbre. Ce papier etudie´ une strategie,´ appelee´ R/A,utilisant un compteur (d’etapes)´ pour alterner entre les phases aleatoires´ (R) ou` l’agent choisit aleatoirement´ une areteˆincidente, et celles (A) ou` l’agent suit le conseil local. Aucune connaissance des parametres` n, d, ou k n’est requise,et l’agent n’a pas besoin de se rappeler par quel lien il est entre´ dans le sommet qu’il occupe. Nous etudions´ les per-formances de cette strategie´ pour deux classes de graphes, extremesˆ pour ce qui est de ...

Sujets

Informations

Publié par
Nombre de lectures 20
Langue English
Signaler un problème
Author manuscript, published in "12èmes Rencontres Francophones sur les Aspects Algorithmiques de Télécommunications (AlgoTel) (2010)"