1. Label-Guided Graph Exploration by a Finite Automaton
- Author
-
David Ilcinkas, David Peleg, Amos Korman, Pierre Fraigniaud, Reuven Cohen, Department of Electrical and Computer Engineering [Boston University] (ECE), Boston University [Boston] (BU), Laboratoire d'informatique Algorithmique : Fondements et Applications (LIAFA), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Algorithmics for computationally intensive applications over wide scale distributed platforms (CEPAGE), Université Sciences et Technologies - Bordeaux 1 (UB)-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Department of Computer Science and Applied Mathematics [Rehovot], Weizmann Institute of Science [Rehovot, Israël], See paper for details, ANR-07-BLAN-0322,ALADDIN,Algorithm Design and Analysis for Implicitly and Incompletely Defined Interaction Networks(2007), Laboratoire de Recherche en Informatique (LRI), Université Paris-Sud - Paris 11 (UP11)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS), Reuven Cohen was supported by the Pacific Theaters Foundation. Pierre Fraigniaud and David Ilcinkas were supported by the project ``PairAPair' of the ACI Masses de Données, the project ``Fragile' of the ACI Sécurité et Informatique, and by the project ``Grand Large' of INRIA., L. Caires, G. Italiano, L. Monteiro, C. Palamidessi, M. Yung, Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), and Université Sciences et Technologies - Bordeaux 1-Inria Bordeaux - Sud-Ouest
- Subjects
Theoretical computer science ,Graph labeling ,Computer science ,Labeling schemes ,Symmetric graph ,[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS] ,0102 computer and information sciences ,02 engineering and technology ,01 natural sciences ,Simplex graph ,law.invention ,Computer Science::Robotics ,Mathematics (miscellaneous) ,Graph exploration ,Graph power ,law ,Clique-width ,Line graph ,String graph ,0202 electrical engineering, electronic engineering, information engineering ,Graph property ,Lattice graph ,Time complexity ,Complement graph ,Mathematics ,Forbidden graph characterization ,Discrete mathematics ,Degree (graph theory) ,Visibility graph ,Voltage graph ,Quartic graph ,Graph theory ,Butterfly graph ,Graph ,Finite graph ,Vertex-transitive graph ,Graph bandwidth ,010201 computation theory & mathematics ,Bounded function ,Cubic graph ,Distributed algorithms ,020201 artificial intelligence & image processing ,Regular graph ,[INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC] ,Null graph ,ACM C.2.1 ,ACM C.2.2 ,ACM C.2.4 ,ACM E.1 - 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 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).
- Published
- 2008