Euler Tour Lock-In Problem in the Rotor-Router Model

DOI10.1007/978-3-642-04355-0_44zbMath1261.68093OpenAlexW1551321261MaRDI QIDQ3646241

Nicolas Hanusse, Adrian Kosowski, Ralf Klasing, Evangelos Bampas, David Ilcinkas, Leszek Gąsieniec

Publication date: 19 November 2009

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-04355-0_44

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Games involving graphs (91A43) Applications of game theory (91A80) Graph theory (including graph drawing) in computer science (68R10)

Related Items (15)

Optimal dispersion on an anonymous ring in the presence of weak Byzantine robots ⋮ Bounds on the cover time of parallel rotor walks ⋮ Coalescing Walks on Rotor-Router Systems ⋮ Time and space optimality of rotor-router graph exploration ⋮ The Range of a Rotor Walk ⋮ The multi-agent rotor-router on the ring: a deterministic alternative to parallel random walks ⋮ Total variation discrepancy of deterministic random walks for ergodic Markov chains ⋮ Deterministic Random Walks for Rapidly Mixing Chains ⋮ Fault-tolerant dispersion of mobile robots ⋮ Distributed Patrolling with Two-Speed Robots (and an Application to Transportation) ⋮ Derandomizing random walks in undirected graphs using locally fair exploration strategies ⋮ Unbounded Discrepancy of Deterministic Random Walks on Grids ⋮ 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 ⋮ Dispersion of mobile robots on directed anonymous graphs

This page was built for publication: Euler Tour Lock-In Problem in the Rotor-Router Model