caa a22 4500 445355115 CHVBK 20180317142857.0 cr unu---uuuuu 170323e20111001xx s 000 0 eng 10.1007/s00446-011-0138-4 doi (NATIONALLICENCE)springer-10.1007/s00446-011-0138-4 Derandomizing random walks in undirected graphs using locally fair exploration strategies [Elektronische Daten] [Colin Cooper, David Ilcinkas, Ralf Klasing, Adrian Kosowski] 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, 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 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 D within time O(D|E|), and in the long run traverses all edges of G with the same frequency. Springer-Verlag, 2011 Graph exploration nationallicence Random walk nationallicence Rotor-router model nationallicence Local knowledge nationallicence Deterministic strategy nationallicence Cooper Colin Department of Computer Science, King's College London, WC2R 2LS, London, UK aut Ilcinkas David LaBRI - Université de Bordeaux - CNRS, 351 cours de la Libération, 33405, Talence, France aut Klasing Ralf LaBRI - Université de Bordeaux - CNRS, 351 cours de la Libération, 33405, Talence, France aut Kosowski Adrian INRIA Bordeaux Sud-Ouest, 351 cours de la Libération, 33405, Talence, France aut Distributed Computing Springer-Verlag 24/2(2011-10-01), 91-99 0178-2770 24:2<91 2011 24 446 https://doi.org/10.1007/s00446-011-0138-4 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s00446-011-0138-4 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Cooper Colin Department of Computer Science, King's College London, WC2R 2LS, London, UK aut NATIONALLICENCE 700 1- Ilcinkas David LaBRI - Université de Bordeaux - CNRS, 351 cours de la Libération, 33405, Talence, France aut NATIONALLICENCE 700 1- Klasing Ralf LaBRI - Université de Bordeaux - CNRS, 351 cours de la Libération, 33405, Talence, France aut NATIONALLICENCE 700 1- Kosowski Adrian INRIA Bordeaux Sud-Ouest, 351 cours de la Libération, 33405, Talence, France aut NATIONALLICENCE 773 0- Distributed Computing Springer-Verlag 24/2(2011-10-01), 91-99 0178-2770 24:2<91 2011 24 446 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer