Time and space optimality of rotor-router graph exploration

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

We consider the problem of exploration of an anonymous, port-labeled, undirected graph with $n$ nodes and $m$ edges and diameter $D$, by a single mobile agent. Initially the agent…