Brief announcement: On the power of one bit in graph exploration without backtracking

Artur Menc (1) , Dominik Pajak (2) , Przemysaaw Uznaski (3)

1 Wroclaw University of Science and Technology
2 Computer Laboratory [Cambridge]
3 Department of Information and Computer Science [Aalto]

We consider a model of a deterministic (Ma,Mw)-agent with Ma bits of internal memory and Mw bits at each node of some graph G that is able to visit vertices and traverse edges of G. The memory at each node is accesible only upon visiting to that node. The goal of the agent is to explore an anonymous and initially unknown G, i.e. visit all its n nodes.

Domains: Distributed, Parallel, and Cluster Computing [cs.DC]

Artur Menc, Dominik Pajak, Przemysaaw Uznaski. Brief announcement: On the power of one bit in graph exploration without backtracking. DISC 2015, Toshimitsu Masuzawa; Koichi Wada, Oct 2015, Tokyo, Japan. ⟨hal-01207849⟩