Derandomizing random walks in undirected graphs using locally fair exploration strategies

DOI10.1007/s00446-011-0138-4zbMath1231.68178OpenAlexW4391922636MaRDI QIDQ661051

Ralf Klasing, Adrian Kosowski, David Ilcinkas, Colin Cooper

Publication date: 6 February 2012

Published in: Distributed Computing (Search for Journal in Brave)

Full work available at URL: https://hal.science/hal-00638229

zbMATH Keywords

random walkgraph explorationrotor-router modeldeterministic strategylocal knowledge

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Random walks on graphs (05C81)

Related Items

Bounds on the cover time of parallel rotor walks, The robot crawler graph process, The multi-agent rotor-router on the ring: a deterministic alternative to parallel random walks, Robustness of the rotor-router mechanism, Random walks which prefer unvisited edges: Exploring high girth even degree expanders in linear time, Lower Bounds for Graph Exploration Using Local Policies, Deterministic walks with choice, Symmetry in domination for hypergraphs with choice

Cites Work

• Unnamed Item
• Unnamed Item
• The cover time of deterministic random walks
• The hitting and cover times of random walks on finite graphs using local degree information
• The power of a pebble: Exploring and mapping directed graphs
• Universal traversal sequences with backtracking.
• A distributed ant algorithm for efficiently patrolling a network
• Graph exploration by a finite automaton
• Deterministic random walks on regular trees
• Multiple cover time
• Tree exploration with logarithmic memory
• Deterministic Random Walks on the Two-Dimensional Grid
• Undirected ST-connectivity in log-space
• Euler Tour Lock-In Problem in the Rotor-Router Model
• Traversing Directed Eulerian Mazes
• Exploring an unknown graph
• Cover times, blanket times, and majorizing measures