Search

Θk-graphs are geometric graphs that appear in the context of graph navigation. The shortest-path metric of these graphs is known to approximate the Euclidean complete graph up to a factor depending on the cone number k and the dimension of the space. TD-Delaunay graphs, a.k.a. triangular-distance Delaunay triangulations, introduced by Chew, have been shown to be plane 2-spanners of the 2D Euclidean complete graph, i.e., the distance in the TD-Delaunay graph between any two points is no more than twice the distance in the plane. Orthogonal surfaces are geometric objects defined from independent sets of points of the Euclidean space. Orthogonal surfaces are well studied in combinatorics (orders, integer programming) and in algebra. From orthogonal surfaces, geometric graphs, called geodesic embeddings can be built. In this paper, we introduce a specific subgraph of the Θ6-graph defined in the 2D Euclidean space, namely the half −Θ6-graph, composed of the even-cone edges of the Θ6-graph. Our main contribution is to show that these graphs are exactly the TD-Delaunay graphs, and are strongly connected to the geodesic embeddings of orthogonal surfaces of coplanar points in the 3D Euclidean space. Using these new bridges between these three fields, we establish: Every Θ6-graph is the union of two spanning TD-Delaunay graphs. In particular, Θ6-graphs are 2-spanners of the Euclidean graph, and the bound of 2 on the stretch factor is the best possible. It was not known that Θ6-graphs are t-spanners for some constant t, and Θ7-graphs were only known to be t-spanners for t ≈ 7.562. Every plane triangulation is TD-Delaunay realizable, i.e., every combinatorial plane graph for which all its interior faces are triangles is the TD-Delaunay graph of some point set in the plane. Such realizability property does not hold for classical Delaunay triangulations. [ABSTRACT FROM AUTHOR]

Two anonymous mobile agents (robots) moving in an asynchronous manner have to meet in an infinite grid of dimension δ> 0, starting from two arbitrary positions at distance at most d. Since the problem is clearly infeasible in such general setting, we assume that the grid is embedded in a δ-dimensional Euclidean space and that each agent knows the Cartesian coordinates of its own initial position (but not the one of the other agent). We design an algorithm permitting the agents to meet after traversing a trajectory of length O(dδpolylogd). This bound for the case of 2d -grids subsumes the main result of [12]. The algorithm is almost optimal, since the Ώ(dδ) lower bound is straightforward. Further, we apply our rendezvous method to the following network design problem. The ports of the δ-dimensional grid have to be set such that two anonymous agents starting at distance at most d from each other will always meet, moving in an asynchronous manner, after traversing a O(dδpolylogd) length trajectory. We can also apply our method to a version of the geometric rendezvous problem. Two anonymous agents move asynchronously in the δ-dimensional Euclidean space. The agents have the radii of visibility of r1 and r2, respectively. Each agent knows only its own initial position and its own radius of visibility. The agents meet when one agent is visible to the other one. We propose an algorithm designing the trajectory of each agent, so that they always meet after traveling a total distance of ]> , where r =  min (r1, r2) and for r ≥ 1. [ABSTRACT FROM AUTHOR]

A mobile robot represented by a point moving in the plane has to explore an unknown flat terrain with impassable obstacles. Both the terrain and the obstacles are modeled as arbitrary polygons. We consider two scenarios: the unlimited vision, when the robot situated at a point p of the terrain explores (sees) all points q of the terrain for which the segment pq belongs to the terrain, and the limited vision, when we require additionally that the distance between p and q be at most 1. All points of the terrain (except obstacles) have to be explored and the performance of an exploration algorithm, called its complexity, is measured by the length of the trajectory of the robot. For unlimited vision we show an exploration algorithm with complexity ]> , where P is the total perimeter of the terrain (including perimeters of obstacles), D is the diameter of the convex hull of the terrain, and k is the number of obstacles. We do not assume knowledge of these parameters. We also prove a matching lower bound showing that the above complexity is optimal, even if the terrain is known to the robot. For limited vision we show exploration algorithms with complexity ]> , where A is the area of the terrain (excluding obstacles). Our algorithms work either for arbitrary terrains, if one of the parameters A or k is known, or for c-fat terrains, where c is any constant (unknown to the robot) and no additional knowledge is assumed. (A terrain ]> with obstacles is c-fat if R/r ≤ c, where R is the radius of the smallest disc containing ]> and r is the radius of the largest disc contained in ]> .) We also prove a matching lower bound ]> on the complexity of exploration for limited vision, even if the terrain is known to the robot. [ABSTRACT FROM AUTHOR]

Two mobile agents (robots) have to meet in an a priori unknown bounded terrain modeled as a polygon, possibly with polygonal obstacles. Robots are modeled as points, and each of them is equipped with a compass. Compasses of robots may be incoherent. Robots construct their routes, but the actual walk of each robot is decided by the adversary that may, e.g., speed up or slow down the robot. We consider several scenarios, depending on three factors: (1) obstacles in the terrain are present, or not, (2) compasses of both robots agree, or not, (3) robots have or do not have a map of the terrain with their positions marked. The cost of a rendezvous algorithm is the worst-case sum of lengths of the robots΄ trajectories until their meeting. For each scenario we design a deterministic rendezvous algorithm and analyze its cost. We also prove lower bounds on the cost of any deterministic rendezvous algorithm in each case. For all scenarios these bounds are tight. [ABSTRACT FROM AUTHOR]

We consider the problem of periodic graph exploration in which a mobile entity with (at most) constant memory, an agent, has to visit all n nodes of an arbitrary undirected graph G in a periodic manner. Graphs are supposed to be anonymous, that is, nodes are unlabeled. However, while visiting a node, the robot has to distinguish between edges incident to it. For each node v the endpoints of the edges incident to v are uniquely identified by different integer labels called port numbers. We are interested in the minimisation of the length of the exploration period. This problem is unsolvable if the local port numbers are set arbitrarily, see [1]. However, surprisingly small periods can be achieved when assigning carefully the local port numbers. Dobrev et al. [2] described an algorithm for assigning port numbers, and an oblivious agent (i.e., an agent with no persistent memory) using it, such that the agent explores all graphs of size n within period 10n. Providing the agent with a constant number of memory bits, the optimal length of the period was proved in [3] to be no more than 3.75n (using a different assignment of the port numbers). In this paper, we improve both these bounds. More precisely, we show a period of length at most ]> for oblivious agents, and a period of length at most 3.5n for agents with constant memory. Finally, we give the first non-trivial lower bound, 2.8n, on the period length for the oblivious case. [ABSTRACT FROM AUTHOR]

The rotor-router model, also called the Propp machine, was first considered as a deterministic alternative to the random walk. It is known that the route in an undirected graph G = (V,E), where |V| = n and |E| = m, adopted by an agent controlled by the rotor-router mechanism forms eventually an Euler tour based on arcs obtained via replacing each edge in G by two arcs with opposite direction. The process of ushering the agent to an Euler tour is referred to as the lock-in problem. In recent work [11] Yanovski et al. proved that independently of the initial configuration of the rotor-router mechanism in G the agent locks-in in time bounded by 2mD, where D is the diameter of G. In this paper we examine the dependence of the lock-in time on the initial configuration of the rotor-router mechanism. The case study is performed in the form of a game between a player ]> intending to lock-in the agent in an Euler tour as quickly as possible and its adversary ]> with the counter objective. First, we observe that in certain (easy) cases the lock-in can be achieved in time O(m). On the other hand we show that if adversary ]> is solely responsible for the assignment of ports and pointers, the lock-in time Ώ(m·D) can be enforced in any graph with m edges and diameter D. Furthermore, we show that if ]> provides its own port numbering after the initial setup of pointers by ]> , the complexity of the lock-in problem is bounded by O(m · min {logm,D}). We also propose a class of graphs in which the lock-in requires time Ώ(m ·logm). In the remaining two cases we show that the lock-in requires time Ώ(m ·D) in graphs with the worst-case topology. In addition, however, we present non-trivial classes of graphs with a large diameter in which the lock-in time is O(m). [ABSTRACT FROM AUTHOR]

We consider the problem of exploring an anonymous undirected graph using an oblivious robot. The studied exploration strategies are designed so that the next edge in the robot΄s walk is chosen using only local information, and so that some local equity (fairness) criterion is satisfied for the adjacent undirected edges. Such strategies can be seen as an attempt to derandomize random walks, and are natural undirected counterparts of the rotor-router model for symmetric directed graphs. The first of the studied strategies, known as Oldest-First (OF), always chooses the neighboring edge for which the most time has elapsed since its last traversal. Unlike in the case of symmetric directed graphs, we show that such a strategy in some cases leads to exponential cover time. We then consider another strategy called Least-Used-First (LUF) which always uses adjacent edges which have been traversed the smallest number of times. We show that any Least-Used-First exploration covers a graph G = (V,E) of diameter ]> within time ]> , and in the long run traverses all edges of G with the same frequency. [ABSTRACT FROM AUTHOR]

We prove that, for the black hole search problem, the pure token model is computationally as powerful as the whiteboard model; furthermore the complexity is exactly the same. More precisely, we prove that a team of two asynchronous agents, each endowed with a single identical pebble (that can be placed only on nodes, and with no more than one pebble per node) can locate the black hole in an arbitrary network of known topology; this can be done with Θ(n logn) moves, where n is the number of nodes, even when the links are not FIFO. [ABSTRACT FROM AUTHOR]

We study deterministic broadcasting in radio networks in the recently introduced framework of network algorithms with advice. We concentrate on the problem of trade-offs between the number of bits of information (size of advice) available to nodes and the time in which broadcasting can be accomplished. In particular, we ask what is the minimum number of bits of information that must be available to nodes of the network, in order to broadcast very fast. For networks in which constant time broadcast is possible under complete knowledge of the network we give a tight answer to the above question: O(n) bits of advice are sufficient but o(n) bits are not, in order to achieve constant broadcasting time in all these networks. This is in sharp contrast with geometric radio networks of constant broadcasting time: we show that in these networks a constant number of bits suffices to broadcast in constant time. For arbitrary radio networks we present a broadcasting algorithm whose time is inverse-proportional to the size of advice. [ABSTRACT FROM AUTHOR]

In the effort to understand the algorithmic limitations of computing by a swarm of robots, the research has focused on the minimal capabilities that allow a problem to be solved. The weakest of the commonly used models is Asynch where the autonomous mobile robots, endowed with visibility sensors (but otherwise unable to communicate), operate in Look-Compute-Move cycles performed asynchronously for each robot. The robots are often assumed (or required to be) oblivious: they keep no memory of observations and computations made in previous cycles. We consider the setting when the robots are dispersed in an anonymous and unlabeled graph, and they must perform the very basic task of exploration: within finite time every node must be visited by at least one robot and the robots must enter a quiescent state. The complexity measure of a solution is the number of robots used to perform the task. We study the case when the graph is an arbitrary tree and establish some unexpected results. We first prove that there are n-node trees where Ώ(n) robots are necessary; this holds even if the maximum degree is 4. On the other hand, we show that if the maximum degree is 3, it is possible to explore with only ]> robots. The proof of the result is constructive. Finally, we prove that the size of the team is asymptotically optimal: we show that there are trees of degree 3 whose exploration requires ]> robots. [ABSTRACT FROM AUTHOR]

We consider the problem of exploring an anonymous unoriented ring by a team of k identical, oblivious, asynchronous mobile robots that can view the environment but cannot communicate. This weak scenario is standard when the spatial universe in which the robots operate is the two-dimentional plane, but (with one exception) has not been investigated before. We indeed show that, although the lack of these capabilities renders the problems considerably more difficult, ring exploration is still possible. We show that the minimum number ρ(n) of robots that can explore a ring of size n is O(logn) and that ρ(n) = Ώ(logn) for arbitrarily large n. On one hand we give an algorithm that explores the ring starting from any initial configuration, provided that n and k are co-prime, and we show that there always exist such k in O(logn). On the other hand we show that Ώ(logn) agents are necessary for arbitrarily large n. Notice that, when k and n are not co-prime, the problem is sometimes unsolvable (i.e., there are initial configurations for which the exploration cannot be done). This is the case, e.g., when k divides n. [ABSTRACT FROM AUTHOR]

Blin et al. (2006) proposed a distributed protocol that enables the smallest number of searchers to clear any unknown asynchronous graph in a decentralized manner. Unknown means that the searchers are provided no a priori information about the graph. However, the strategy that is actually performed lacks of an important property, namely the monotonicity. That is, the clear part of the graph may decrease at some steps of the execution of the protocol. Actually, the protocol of Blin et al. is executed in exponential time. Nisse and Soguet (2007) proved that, in order to ensure the smallest number of searchers to clear any n-node graph in a monotone way, it is necessary and sufficient to provide Θ(n logn) bits of information to the searchers by putting short labels on the nodes of the graph. This paper deals with the smallest number of searchers that are necessary and sufficient to monotoneously clear any graph in a decentralized manner, when the searchers have no a priori information about the graph. The distributed graph searching problem considers a team of searchers that is aiming at clearing any connected contaminated graph. The clearing of the graph is required to be connected, i.e., the clear part of the graph must remain permanently connected, and monotone, i.e., the clear part of the graph only grows. The search number of a graph G is the smallest number of searchers necessary to clear G in a monotone connected way in centralized settings. We prove that any distributed protocol aiming at clearing any unknown n-node graph in a monotone connected way, in decentralized settings, has competitive ratio ]> . That is, we prove that, for any distributed protocol ]> , there exists a constant c such that for any sufficiently large n, there exists a n-node graph G such that ]> requires at least searchers to clear G. Moreover, we propose a distributed protocol that allows searchers to clear any unknown asynchronous n-node graph G in a monotone connected way. [ABSTRACT FROM AUTHOR]

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]

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]

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]

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]