Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
9657750 | Theoretical Computer Science | 2005 | 14 Pages |
Abstract
A finite automaton, simply referred to as a robot, has to explore a graph whose nodes are unlabeled and whose edge ports are locally labeled at each node. The robot has no a priori knowledge of the topology of the graph or of its size. Its task is to traverse all the edges of the graph. We first show that, for any K-state robot and any d⩾3, there exists a planar graph of maximum degree d with at most K+1 nodes that the robot cannot explore. This bound improves all previous bounds in the literature. More interestingly, we show that, in order to explore all graphs of diameter D and maximum degree d, a robot needs Ω(Dlogd) memory bits, even if we restrict the exploration to planar graphs. This latter bound is tight. Indeed, a simple DFS up to depth D+1 enables a robot to explore any graph of diameter D and maximum degree d using a memory of size O(Dlogd) bits. We thus prove that the worst case space complexity of graph exploration is Î(Dlogd) bits.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Pierre Fraigniaud, David Ilcinkas, Guy Peer, Andrzej Pelc, David Peleg,