TY - GEN
T1 - Traversing directed eulerian mazes
T2 - 26th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2000
AU - Bhatt, Sandeep
AU - Even, Shimon
AU - Greenberg, David
AU - Tayar, Rafi
N1 - Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 2000.
PY - 2000
Y1 - 2000
N2 - 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(v)) in every vertex v.
AB - 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(v)) in every vertex v.
UR - http://www.scopus.com/inward/record.url?scp=0242602650&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0242602650&partnerID=8YFLogxK
U2 - 10.1007/3-540-40064-8_5
DO - 10.1007/3-540-40064-8_5
M3 - Conference contribution
AN - SCOPUS:0242602650
SN - 3540411836
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 35
EP - 46
BT - Graph-Theoretic Concepts in Computer Science - 26th International Workshop, WG 2000 Konstanz, Germany, June 15-17, 2000 Proceedings
A2 - Brandes, Ulrik
A2 - Wagner, Dorothea
Y2 - 15 June 2000 through 17 June 2000
ER -