Home  Issues  Aims and Scope  Instructions for Authors 
DOI: 10.7155/jgaa.00049
Traversing Directed Eulerian Mazes
Vol. 6, no. 2, pp. 157173, 2002. Regular paper.
Abstract 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 finitestate 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 ·E) edge traversals, while the advanced
algorithm traverses every edge three times. Let d_{out}(v) be
the outdegree of vertex v. The algorithms use, at each vertex
v, a local memory of size O(logd_{out}(v)).
