\input zb-basic
\input zb-ioport
\iteman{io-port 05212081}
\itemau{G\c asieniec, Leszek; Klasing, Ralf; Martin, Russell; Navarra, Alfredo; Zhang, Xiaohui}
\itemti{Fast periodic graph exploration with constant memory.}
\itemso{Prencipe, Giuseppe (ed.) et al., Structural information and communication complexity. 14th international colloquium, SIROCCO 2007, Castiglioncello, Italy, June 5--8, 2007. Proceedings. Berlin: Springer (ISBN 978-3-540-72918-1/pbk). Lecture Notes in Computer Science 4474, 26-40 (2007).}
\itemab
Summary: We consider the problem of periodic exploration of all nodes in undirected graphs by using a finite state automaton called later a robot. The robot, using a constant number of states (memory bits), must be able to explore any unknown anonymous graph. The nodes in the graph are neither labelled nor colored. However, while visiting a node $v$ the robot can distinguish between edges incident to it. The edges are ordered and labelled by consecutive integers $1,\dots,d(v)$ called port numbers, where $d(v)$ is the degree of $v$. Periodic graph exploration requires that the automaton has to visit every node infinitely many times in a periodic manner. Note that the problem is unsolvable if the local port numbers are set arbitrarily. In this context, we are looking for the minimum function $\pi (n)$, such that, there exists an efficient deterministic algorithm for setting the local port numbers allowing the robot to explore all graphs of size $n$ along a traversal route with the period $\pi (n)$. {\it S. Dobrev} et al. proved in [``Finding short right-hand-on-the-wall walks in graphs'', Lect.~Notes~Comput.~Sci.~3499, 127--139 (2005; Zbl 1085.68106)] that for oblivious robots $\pi (n) \leq 10n$. Recently Ilcinkas proposed another port labelling algorithm for robots equipped with two extra memory bits, see [{\it D. Ilcinkas}, ``Setting port numbers for fast graph exploration'', Lect.~Notes~Comput.~Sci.~4056, 59--69 (2006; Zbl 1222.68124)], where the exploration period $\pi (n) \leq 4n - 2$. In the same paper, it is conjectured that the bound $4n - O(1)$ is tight even if the use of larger memory is allowed. In this paper, we disprove this conjecture presenting an efficient deterministic algorithm arranging the port numbers, such that, the robot equipped with a constant number of bits is able to complete the traversal period in $\pi (n) \leq 3.75n - 2$ steps hence decreasing the existing upper bound. This reduces the gap with the lower bound of $\pi (n) \geq 2n - 2$ holding for any robot.
\itemrv{~}
\itemcc{}
\itemut{}
\itemli{doi:10.1007/978-3-540-72951-8\_4}
\end