Search

We consider the task of exploring graphs with anonymous nodes by a team of non-cooperative robots, modeled as finite automata. For exploration to be completed, each edge of the graph has to be traversed by at least one robot. In this paper, the robots have no a priori knowledge of the topology of the graph, nor of its size, and we are interested in the amount of memory the robots need to accomplish exploration, We introduce the so-called reduced automata technique, and we show how to use this technique for deriving several space lower bounds for exploration. Informally speaking, the reduced automata technique consists in reducing a robot to a simpler form that preserves its "core" behavior on some graphs. Using this technique, we first show that any set of q≥ 1 non-cooperative robots, requires $\Omega(\log(\frac{n}{q}))$ memory bits to explore all n-node graphs. The proof implies that, for any set of qK-state robots, there exists a graph of size O(qK) that no robot of this set can explore, which improves the O(KO(q)) bound by Rollik (1980). Our main result is an application of this latter result, concerning terminating graph exploration with one robot, i.e., in which the robot is requested to stop after completing exploration. For this task, the robot is provided with a pebble, that it can use to mark nodes (without such a marker, even terminating exploration of cycles cannot be achieved). We prove that terminating exploration requires Ω(log n) bits of memory for a robot achieving this task in all n-node graphs. [ABSTRACT FROM AUTHOR]

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 v are given port numbers from 1 to dv, where dv is the degree of v. 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 mimimum function π(n) such that there exist an algorithm for setting the local orientation, and a finite automaton using it, such that the automaton explores all graphs of size n within the period π(n)? The best result so far is the upper bound π(n) ≤10n, by Dobrev et al. [SIROCCO 2005], using an automaton with no memory (i.e. only one state). In this paper we prove a better upper bound π(n) ≤4n. Our automaton uses three states but performs periodic exploration independently of its starting position and initial state. [ABSTRACT FROM AUTHOR]

We study the amount of knowledge about the network that is required in order to efficiently solve a task concerning this network. The impact of available information on the efficiency of solving network problems, such as communication or exploration, has been investigated before but assumptions concerned availability of particular items of information about the network, such as the size, the diameter, or a map of the network. In contrast, our approach is quantitative: we investigate the minimum number of bits of information (minimum oracle size) that has to be given to an algorithm in order to perform a task with given efficiency. We illustrate this quantitative approach to available knowledge by the task of tree exploration. A mobile entity (robot) has to traverse all edges of an unknown tree, using as few edge traversals as possible. The quality of an exploration algorithm ${\cal A}$ is measured by its competitive ratio, i.e., by comparing its cost (number of edge traversals) to the length of the shortest path containing all edges of the tree. Depth-First-Search has competitive ratio 2 and, in the absence of any information about the tree, no algorithm can beat this value. We determine the minimum number of bits of information that has to be given to an exploration algorithm in order to achieve competitive ratio strictly smaller than 2. Our main result establishes an exact threshold oracle size that turns out to be roughly loglogD, where D is the diameter of the tree. More precisely, for any constant c, we construct an exploration algorithm with competitive ratio smaller than 2, using an oracle of size at most loglogD -c, and we show that every algorithm using an oracle of size loglogD -g(D), for any function g unbounded from above, has competitive ratio at least 2. [ABSTRACT FROM AUTHOR]

A finite automaton, simply referred to as a robot, has to explore a graph, i.e., visit all the nodes of the graph. The robot has no a priori knowledge of the topology of the graph or of its size. It is known that, for any k-state robot, there exists a (k+1)-node graph of maximum degree 3 that the robot cannot explore. This paper considers the effects of allowing the system designer to add short labels to the graph nodes in a preprocessing stage, and using these labels to guide 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 , and a way to color in black or white the nodes of any bounded-degree graph G, so that 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]

This paper deals with compact label-based representations for trees. Consider an n-node undirected connected graph G with a predefined numbering on the ports of each node. The all-ports tree labeling gives each node v of G a label containing the port numbers of all the tree edges incident to v. The upward tree labeling labels each node v by the number of the port leading from v to its parent in the tree. Our measure of interest is the worst case and total length of the labels used by the scheme, denoted Mup(T) and Sup(T) for and Mall(T) and Sall(T) for . The problem studied in this paper is the following: Given a graph G and a predefined port labeling for it, with the ports of each node v numbered by , select a rooted spanning tree for G minimizing (one of) these measures. We show that the problem is polynomial for Mup(T), Sup(T) and Sall(T) but NP-hard for Mall(T) (even for 3-regular planar graphs). We show that for every graph G and port numbering there exists a spanning tree T for which Sup(T) = O(n log log n). We give a tight bound of O(n) in the cases of complete graphs with arbitrary labeling and arbitrary graphs with symmetric port assignments. We conclude by discussing some applications for our tree representation schemes. [ABSTRACT FROM AUTHOR]

We consider the task of exploring graphs with anonymous nodes by a team of non-cooperative robots modeled as finite automata. These robots have no a priori knowledge of the topology of the graph, or of its size. Each edge has to be traversed by at least one robot. We first show that, for any set of q non-cooperative K-state robots, there exists a graph of size O(qK) that no robot of this set can explore. This improves the O(KO(q)) bound by Rollik (1980). Our main result is an application of this improvement. It concerns exploration with stop, in which one robot has to explore and stop after completing exploration. For this task, the robot is provided with a pebble, that it can use to mark nodes. We prove that exploration with stop requires Ω(log n) bits for the family of graphs with at most n nodes. On the other hand, we prove that there exists an exploration with stop algorithm using a robot with O(D log Δ) bits of memory to explore all graphs of diameter at most D and degree at most Δ. Keywords: Graph exploration, finite automaton, robot, mobile agent. [ABSTRACT FROM AUTHOR]