Search

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). [ABSTRACT FROM AUTHOR]

Abstract: We consider the problem of periodic graph exploration by a finite automaton in which an automaton with a constant number of states has to explore all unknown anonymous graphs of arbitrary size and arbitrary maximum degree. In anonymous graphs, nodes are not labeled but edges are labeled in a local manner (called local orientation) so that the automaton is able to distinguish them. Precisely, the edges incident to a node are given port numbers from to , where is the degree of . Periodic graph exploration means visiting every node infinitely often. We are interested in the length of the period, i.e., the maximum number of edge traversals between two consecutive visits of any node by the automaton in the same state and entering the node by the same port. This problem is unsolvable if local orientations are set arbitrarily. Given this impossibility result, we address the following problem: what is the minimum function such that there exists an algorithm for setting the local orientation, and a finite automaton using it, such that the automaton explores all graphs of size within the period ? The best result so far is the upper bound , by Dobrev et al. [S. Dobrev, J. Jansson, K. Sadakane, W.-K. Sung, Finding short right-hand-on-the-wall walks in graphs, in: 12th Colloquium on Structural Information and Communication Complexity, SIROCCO, in: LNCS, vol. 3499, 2005, pp. 127–139], using an automaton with no memory (i.e. only one state). In this paper we prove a better upper bound . Our automaton uses three states but performs periodic exploration independently of its starting position and initial state. [Copyright &y& Elsevier]

Abstract: A mobile agent (robot), modeled as a finite automaton, has to visit all nodes of a regular graph. How does the memory size of the agent (the number of states of the automaton) influence its exploration capability? In particular, does every increase of the memory size enable an agent to explore more graphs? We give a partial answer to this problem by showing that a strict gain of the exploration power can be obtained by a polynomial increase of the number of states. We also show that, for automata with few states, the increase of memory by even one state results in the capability of exploring more graphs. [Copyright &y& Elsevier]

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 , there exists a planar graph of maximum degree d with at most 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 memory bits, even if we restrict the exploration to planar graphs. This latter bound is tight. Indeed, a simple DFS up to depth enables a robot to explore any graph of diameter D and maximum degree d using a memory of size bits. We thus prove that the worst case space complexity of graph exploration is bits. [Copyright &y& Elsevier]

Abstract: We consider the problem of periodic graph exploration in which a mobile entity with constant memory, an agent, has to visit all nodes of an input simple, connected, undirected graph in a periodic manner. Graphs are assumed to be anonymous, that is, nodes are unlabeled. While visiting a node, the agent may distinguish between the edges incident to it; for each node , the endpoints of the edges incident to are uniquely identified by different integer labels called port numbers. We are interested in algorithms for assigning the port numbers together with traversal algorithms for agents using these port numbers to obtain short traversal periods. Periodic graph exploration is unsolvable if the port numbers are set arbitrarily; see Budach (1978) . However, surprisingly small periods can be achieved by carefully assigning the port numbers. Dobrev et al. (2005) described an algorithm for assigning port numbers and an oblivious agent (i.e., an agent with no memory) using it, such that the agent explores any graph with  nodes within the period . When the agent has access to a constant number of memory bits, the optimal length of the period was proved in Gąsieniec et al. (2008)  to be no more than (using a different assignment of the port numbers and a different traversal algorithm). In this paper, we improve both these bounds. More precisely, we show how to achieve a period length of at most for oblivious agents and a period length of at most for agents with constant memory. To obtain our results, we introduce a new, fast graph decomposition technique called a three-layer partition that may also be useful for solving other graph problems in the future. Finally, we present the first non-trivial lower bound, , on the period length for the oblivious case. [Copyright &y& Elsevier]