Derandomizing random walks in undirected graphs using locally fair exploration strategies
ILCINKAS, David
Algorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
Combinatoire et Algorithmique
Algorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
Combinatoire et Algorithmique
KLASING, Ralf
Algorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
Combinatoire et Algorithmique
Voir plus >
Algorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
Combinatoire et Algorithmique
ILCINKAS, David
Algorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
Combinatoire et Algorithmique
Algorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
Combinatoire et Algorithmique
KLASING, Ralf
Algorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
Combinatoire et Algorithmique
Algorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
Combinatoire et Algorithmique
KOSOWSKI, Adrian
Algorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
Combinatoire et Algorithmique
< Réduire
Algorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
Combinatoire et Algorithmique
Langue
en
Article de revue
Ce document a été publié dans
Distributed Computing. 2011, vol. 24, n° 2, p. 91-99
Springer Verlag
Résumé en anglais
We consider the problem of exploring an anonymous undirected graph using an oblivious robot. The studied exploration strategies are designed so that the next edge in the robot's walk is chosen using only local information, ...Lire la suite >
We consider the problem of exploring an anonymous undirected graph using an oblivious robot. The studied exploration strategies are designed so that the next edge in the robot's walk is chosen using only local information, and so that some local equity (fairness) criterion is satisfied for the adjacent undirected edges. Such strategies can be seen as an attempt to derandomize random walks, and are natural counterparts for undirected graphs of the rotor-router model for symmetric directed graphs. The first of the studied strategies, known as Oldest-First (OF), always chooses the neighboring edge for which the most time has elapsed since its last traversal. Unlike in the case of symmetric directed graphs, we show that such a strategy in some cases leads to exponential cover time. We then consider another strategy called Least-Used-First (LUF) which always uses adjacent edges which have been traversed the smallest number of times. We show that any Least-Used-First exploration covers a graph G=(V,E) of diameter diam within time O(diam|E|), and in the long run traverses all edges of G with the same frequency.< Réduire
Mots clés en anglais
Random walk
Graph exploration
Project ANR
Algorithm Design and Analysis for Implicitly and Incompletely Defined Interaction Networks - ANR-07-BLAN-0322
Origine
Importé de halUnités de recherche