Traversing directed Eulerian mazes

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

Research output: Contribution to journalReview articlepeer-review

20 Scopus citations

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)).

Original languageEnglish
Pages (from-to)157-173
Number of pages17
JournalJournal of Graph Algorithms and Applications
Volume6
Issue number2
DOIs
StatePublished - 2002

Fingerprint

Dive into the research topics of 'Traversing directed Eulerian mazes'. Together they form a unique fingerprint.

Cite this