Geodesic
Traversing Directed Eulerian Mazes
Journal of Graph Algorithms and Applications, Tome 6 (2002) no. 2, pp. 157-173.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

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)). 
@article{JGAA_2002_6_2_a0,
     author = {S. Bhatt and Shimon Even and D. Greenberg and R. Tayar},
     title = {Traversing {Directed} {Eulerian} {Mazes}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {157--173},
     publisher = {mathdoc},
     volume = {6},
     number = {2},
     year = {2002},
     doi = {10.7155/jgaa.00049},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00049/}
}
TY  - JOUR
AU  - S. Bhatt
AU  - Shimon Even
AU  - D. Greenberg
AU  - R. Tayar
TI  - Traversing Directed Eulerian Mazes
JO  - Journal of Graph Algorithms and Applications
PY  - 2002
SP  - 157
EP  - 173
VL  - 6
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00049/
DO  - 10.7155/jgaa.00049
LA  - en
ID  - JGAA_2002_6_2_a0
ER  - 
%0 Journal Article
%A S. Bhatt
%A Shimon Even
%A D. Greenberg
%A R. Tayar
%T Traversing Directed Eulerian Mazes
%J Journal of Graph Algorithms and Applications
%D 2002
%P 157-173
%V 6
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00049/
%R 10.7155/jgaa.00049
%G en
%F JGAA_2002_6_2_a0
S. Bhatt; Shimon Even; D. Greenberg; R. Tayar. Traversing Directed Eulerian Mazes. Journal of Graph Algorithms and Applications, Tome 6 (2002) no. 2, pp. 157-173. doi : 10.7155/jgaa.00049. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00049/

Cité par Sources :