COOPER, Colin; ILCINKAS, David; KLASING, Ralf; KOSOWSKI, Adrian

doi:10.1007/978-3-642-02930-1_34

Metadatos

Licencia de uso del documento

COOPER, Colin
Department of Computer Science [DCS]

ILCINKAS, David
Laboratoire Bordelais de Recherche en Informatique [LaBRI]
Algorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]

KLASING, Ralf
Algorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
Combinatoire et Algorithmique

Idioma

Communication dans un congrès

Este ítem está publicado en

Proceedings of the 36th International Colloquium on Automata, Languages and Programming, Proceedings of the 36th International Colloquium on Automata, Languages and Programming, ICALP 2009, 2009-07. 2009-07, vol. 5556, p. 411-422

Springer Berlin / Heidelberg

Resumen en inglés

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 undirected counterparts 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.< Leer menos

Palabras clave

graph exploration : Propp machine

URI

https://oskar-bordeaux.fr/handle/20.500.12278/198462

DOI

http://dx.doi.org/10.1007/978-3-642-02930-1_34

Proyecto ANR

ALgorithmique des Plates-formes A Grande Echelle - ANR-05-MMSA-0006

Orígen

Importado de Hal

Centros de investigación

Laboratoire Bordelais de Recherche en Informatique (LaBRI) - UMR 5800