Tree exploration with little memory

Abstract

A robot with k-bit memory has to explore a tree whose nodes are unlabeled and edge ports are locally labeled at each node. The robot has no a priori knowledge of the topology of the tree or of its size, and its aim is to traverse all the edges. While O(logA) bits of memory suffice to explore any tree of maximum degree A if stopping is not required, we show that bounded memory is not sufficient to explore with stop all trees of bounded degree (indeed f~(logloglog n) bits of memory are needed for some such trees of size n). For the more demanding task requiring to stop at the starting node after completing exploration, we show a sharper lower bound f~(log n) on required memory size, and present an algorithm to accomplish this task with O(log 2 n)-bit memory, for all n-node trees.