Bhatt, S.; Even, S.; Greenberg, D.; Tayar, R.

Traversing directed Eulerian mazes

J. Graph Algorithms Appl. 6(2), 157-173 (2002)


Summary: The paper describes two algorithms for threading unknown, finite directed Eulerian mazes. Each of these algorithms is performed by a traveling robot whose control is a finite-state automaton. It is assumed that each vertex has a circular list of its outgoing edges. The items of this list are called exits. Each of the algorithms puts in one of the exits of each vertex a scan pebble. These pebbles can be used by a simple robot as traffic signals, which allow it to traverse an Eulerian cycle of the maze.For a directed graph (maze) $G(V, E)$, the simple algorithm performs $O(|V | \cdot |E|)$ edge traversals, while the advanced algorithm traverses every edge three times. Let $dout(v)$ be the out-degree of vertex v. The algorithms use, at each vertex v, a local memory of size O(log $dout(v))$. Communicated by S. Khuller: submitted January 2002; revised June 2002 Work by S. Even supported by the Fund for the Promotion of Research at the Technion.