Derandomizing random walks in undirected graphs using locally fair exploration strategies

摘要: We consider the problem of exploring an anonymous undirected graph using oblivious robot. The studied exploration strategies are designed so that next edge in robot’s walk is chosen only local information, and some equity (fairness) criterion satisfied for adjacent edges. Such can be seen as attempt to derandomize random walks, natural counterparts graphs rotor-router model symmetric directed graphs. first strategies, known Oldest-First, always chooses neighboring which most time has elapsed since its last traversal. Unlike case graphs, we show such a strategy cases leads exponential cover time. then another called Least-Used-First uses edges have been traversed smallest number times. any covers G = (V, E) diameter D within O(D|E|), long run traverses all with same frequency.