Bounds on the cover time of parallel rotor walks

DOI10.1016/j.jcss.2016.01.004zbMath1338.68216OpenAlexW2293335601MaRDI QIDQ269498

Dariusz Dereniowski, Adrian Kosowski, Dominik Pająk, Przemysław Uznański

Publication date: 18 April 2016

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2016.01.004

zbMATH Keywords

derandomizationcollaborative robotscover timedistributed graph explorationparallel random walksrotor-router

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20) Artificial intelligence for robotics (68T40)

Related Items (3)

Searching efficiency of multiple walkers on the weighted networks ⋮ The cover time of deterministic random walks for general transition probabilities ⋮ Does adding more agents make a difference? A case study of cover time for the rotor-router

Cites Work

• Tight bounds for the cover time of multiple random walks
• The cover time of deterministic random walks
• Derandomizing random walks in undirected graphs using locally fair exploration strategies
• Strong spherical asymptotics for rotor-router aggregation and the divisible sandpile
• A spectrum of time-space trade-offs for undirected \(s-t\) connectivity
• A distributed ant algorithm for efficiently patrolling a network
• The rotor-router shape is spherical
• Bounds on the Cover Time of Parallel Rotor Walks
• Simulating a Random Walk with Constant Error
• Deterministic Random Walks on the Two-Dimensional Grid
• How Well Do Random Walks Parallelize?
• Euler Tour Lock-In Problem in the Rotor-Router Model
• Traversing Directed Eulerian Mazes
• Does Adding More Agents Make a Difference? A Case Study of Cover Time for the Rotor-Router
• The multi-agent rotor-router on the ring
• Expansion and the cover time of parallel random walks
• Many Random Walks Are Faster Than One
• Spherical asymptotics for the rotor-router model in $\mathbb{Z}^d$

This page was built for publication: Bounds on the cover time of parallel rotor walks