The multi-agent rotor-router on the ring: a deterministic alternative to parallel random walks
From MaRDI portal
Publication:2407630
DOI10.1007/s00446-016-0282-yzbMath1419.68030OpenAlexW2520039216WikidataQ59603455 ScholiaQ59603455MaRDI QIDQ2407630
Dominik Pająk, Adrian Kosowski, Thomas Sauerwald, Ralf Klasing
Publication date: 6 October 2017
Published in: Distributed Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00446-016-0282-y
Graph theory (including graph drawing) in computer science (68R10) Distributed systems (68M14) Random walks on graphs (05C81)
Related Items (1)
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
- A spectrum of time-space trade-offs for undirected \(s-t\) connectivity
- A distributed ant algorithm for efficiently patrolling a network
- Robustness of the rotor-router mechanism
- Graph exploration by a finite automaton
- Improved Analysis of Deterministic Load-Balancing Schemes
- Simulating a Random Walk with Constant Error
- Disks, Balls, and Walls: Analysis of a Combinatorial Game
- Deterministic Random Walks on the Two-Dimensional Grid
- Undirected connectivity in log-space
- How Well Do Random Walks Parallelize?
- Euler Tour Lock-In Problem in the Rotor-Router Model
- A note on the last new vertex visited by a random walk
- Trading Space for Time in Undirected s-t Connectivity
- 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
- Memory Efficient Anonymous Graph Exploration
This page was built for publication: The multi-agent rotor-router on the ring: a deterministic alternative to parallel random walks
