Traversing Directed Eulerian Mazes
| Autor: | Rafi Tayar, Sandeep N. Bhatt, Shimon Even, David S. Greenberg |
|---|---|
| Rok vydání: | 2002 |
| Předmět: |
Vertex (graph theory)
Traverse General Computer Science Computer science Eulerian path Edge (geometry) Computer Science Applications Theoretical Computer Science Automaton Combinatorics symbols.namesake Computational Theory and Mathematics symbols Robot Geometry and Topology SIMPLE algorithm MathematicsofComputing_DISCRETEMATHEMATICS |
| Zdroj: | Journal of Graph Algorithms and Applications. 6:157-173 |
| ISSN: | 1526-1719 |
| Popis: | 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 υ. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|