Abstract. A finite automaton, simply referred to as a robot, has to explore a graph, that is, visit all the nodes of the graph. The robot has no a priori knowledge of the topology of the graph, nor of its size. It is known that for any k-state robot, there exists a graph of maximum degree 3 that the robot cannot explore. This article considers the effects of allowing the system designer to add short labels to the graph nodes in a preprocessing stage, for helping the exploration by the robot. We describe an exploration algorithm that, given appropriate 2-bit labels (in fact, only 3-valued labels), allows a robot to explore all graphs. Furthermore, we describe a suitable labeling algorithm for generating the R. Cohen was supported by the Pacific Theaters Foundation. P. Fraigniaud was supported by the project "PairAPair" of the ACI Masses de Données, project "Fragile" of the ACI Sécurité et Informatique, and project "Grand Large" of INRIA. A. Korman was supported in part by the project "GANG" of INRIA. D. Peleg was supported in part by a grant from the Israel Science Foundation. Authors' addresses: R. Cohen, Department of Electrical and Computer Engineering, Boston University, Boston, MA, e-mail: cohenr@bu.edu; P. Fraigniaud, CNRS and Université Paris Diderot -Paris 7, France, e-mail: pierre@liafa.jussieu.fr; D. Ilcinkas, CNRS and Université Bordeaux I, France, e-mail: david.ilcinkas@labri.fr; A. Korman, CNRS and Université Paris Diderot -Paris 7, France, e-mail: amos.korman@liafa.jussieu.fr; D. Peleg, Department of Computer Science, The Weizmann Institute, Rehovot, Israel, e-mail: david.peleg@weizmann.ac.il. Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or direct commercial advantage and that copies show this notice on the first page or initial screen of a display along with the full citation. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, to republish, to post on servers, to redistribute to lists, or to use any component of this work in other works requires prior specific permission and/or a fee. Permissions may be requested from Publications Dept., ACM, Inc., 2 Penn Plaza, Suite 701, New York, NY 10121-0701 USA, fax +1 ( required labels in linear time. We also show how to modify our labeling scheme so that a robot can explore all graphs of bounded degree, given appropriate 1-bit labels. In other words, although there is no robot able to explore all graphs of maximum degree 3, there is a robot R, and a way to color in black or white the nodes of any bounded-degree graph G, so that R can explore the colored graph G. Finally, we give impossibility results regarding graph exploration by a robot with no internal memory (i.e., a single-state automaton).
It is proved in REF that there is an algorithm coloring the nodes using only three colors, and a finite automaton using this coloring which can explore all graphs.
Label-guided graph exploration by a finite automaton
TALG
Mathematics Computer Science