Journal of Graph Algorithms and Applications
http://jgaa.info ISSN: 1526-1719
DOI: 10.7155/jgaa.00049 Traversing Directed Eulerian Mazes S. Bhatt , Shimon Even , D. Greenberg , and R. Tayar 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(logdout(v)).
|
Revised: June 2002. Submitted: January 2002. Communicated by Samir Khuller |
Journal of Graph Algorithms and Applications |