Traversing Directed Eulerian Mazes

Abstract

Two algorithms for threading directed Eulerian mazes are described. Each of these algorithms is performed by a traveling robot whose control is a finite-state automaton. Each of the algorithms puts one pebble in one of the exits of every vertex. These pebbles indicate an Eulerian cycle of the maze. The simple algorithm performs O(|V| ċ |E|) edge traversals, while the advanced one traverses every edge three times. Both algorithms use memory of size O(log dout(υ)) in every vertex υ.