Time and space optimality of rotor-router graph exploration

DOI10.1016/J.IPL.2017.06.010zbMath1414.68039arXiv1502.05545OpenAlexW2207472552MaRDI QIDQ2398496

Dominik Pająk, Przemysław Uznański, Artur Menc

Publication date: 16 August 2017

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1502.05545

zbMATH Keywords

distributed computinggraph explorationmemory complexity

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (4)

Optimal dispersion on an anonymous ring in the presence of weak Byzantine robots ⋮ Zero-memory graph exploration with unknown inports ⋮ Invited paper: One bit agent memory is enough for snap-stabilizing perpetual exploration of cactus graphs with distinguishable cycles ⋮ Dispersion of mobile robots on directed anonymous graphs

Cites Work

• A distributed ant algorithm for efficiently patrolling a network
• Euler Tour Lock-In Problem in the Rotor-Router Model

This page was built for publication: Time and space optimality of rotor-router graph exploration