Label-guided graph exploration by a finite automaton
Label-guided graph exploration by a finite automaton
复制标题
有限自动机的标签引导图探索
DOI：
--
复制
发表时间：
2005
期刊：
影响因子：
--
通讯作者：
D. Peleg
中科院分区：
文献类型：
--
作者：
Reuven Cohen;P. Fraigniaud;D. Ilcinkas;Amos Korman;D. Peleg
有限自动机，简称为机器人，必须探索图，即访问图的所有节点。机器人既不知道图的拓扑结构，也不知道图的大小。已知对于任何k状态机器人，存在机器人不能探索的最大度为3的图。本文考虑了允许系统设计者在预处理阶段向图节点添加短标签的效果，以帮助机器人进行探索。我们描述了一个探索算法，给出适当的2位标签（事实上，只有3值标签），允许机器人探索所有的图。此外，我们描述了一个合适的标记算法，用于在线性时间内生成所需的标签。我们还展示了如何修改我们的标签方案，使机器人可以探索所有的图形有界度，适当的1位标签。换句话说，虽然没有机器人能够探索所有最大度为3的图，但存在机器人R，以及将任何有界度图G的节点着色为黑色或白色的方法，使得R可以探索着色图G。最后，我们给出了关于没有内部存储器的机器人进行图探索的不可能性结果（即，单态自动机）。
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).
使用对数内存进行树探索
影响因子：
1.3
作者：
Ambühl C
通讯作者：
Ambühl C