Traversing Directed Eulerian Mazes
Vol. 6, no. 2, pp. 157-173, 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 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| ·|
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)).