Search

We study the problem of exploration by a mobile entity (agent) of a class of highly dynamic networks, namely the carrier graphs (the C-graphs, modeling public transportation systems, among others). These are defined by a set of carriers following infinitely their prescribed route along the stations of the network. Flocchini, Mans, and Santoro [9] studied this problem in the case when the agent must always travel on the carriers and thus cannot wait on a station. They described the necessary and sufficient conditions for the problem to be solvable and proved that the optimal worst-case number of time units (and thus of moves) to explore a n -node C-graph of k carriers and maximal period p is in Θ (k p 2) in the general case. In this paper, we study the impact of the ability to wait at the stations. We exhibit the necessary and sufficient conditions for the problem to be solvable in this context, and we prove that waiting at the stations allows the agent to reduce the optimal worst-case number of moves by a multiplicative factor of at least Θ (p) , while the worst-case time complexity is reduced to Θ (n p). (In any connected carrier graph, we have n ≤ k p.) We also show some complementary optimal results in specific cases (same period for all carriers, highly connected C-graphs). Finally this new ability allows the agent to completely map the C-graph, in addition to just exploring it. [ABSTRACT FROM AUTHOR]

In this paper, we study the T-interval-connected dynamic graphs from the point of view of the time necessary and sufficient for their exploration by a mobile entity (agent). A dynamic graph (more precisely, an evolving graph) is T-interval-connected (T ≥ 1) if, for every window of T consecutive time steps, there exists a connected spanning subgraph that is stable (always present) during this period. This property of connection stability over time was introduced by Kuhn, Lynch and Oshman (Kuhn et al. 14) (STOC 2010). We focus on the case when the underlying graph is a ring of size n, and we show that the worst-case time complexity for the exploration problem is 2n − T − Θ(1) time units if the agent knows the dynamics of the graph, and n+nmax{1,T−1}(δ−1)±Θ(δ) time units otherwise, where δ is the maximum time between two successive appearances of an edge. [ABSTRACT FROM AUTHOR]

Abstract: We study the amount of knowledge about a communication network that must be given to its nodes in order to efficiently disseminate information. Our approach is quantitative: we investigate the minimum total number of bits of information (minimum size of advice) that has to be available to nodes, regardless of the type of information provided. We compare the size of advice needed to perform broadcast and wakeup (the latter is a broadcast in which nodes can transmit only after getting the source information), both using a linear number of messages (which is optimal). We show that the minimum size of advice permitting the wakeup with a linear number of messages in an n-node network, is , while the broadcast with a linear number of messages can be achieved with advice of size . We also show that the latter size of advice is almost optimal: no advice of size can permit to broadcast with a linear number of messages. Thus an efficient wakeup requires strictly more information about the network than an efficient broadcast. [Copyright &y& Elsevier]

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]

The behavior of rational selfish agents has been classically studied in the framework of strategic games in which each player has a set of possible actions, players choose actions simultaneously and the payoff for each player is determined by the matrix of the game. However, in many applications, players choose actions asynchronously, and simultaneity of this process is not guaranteed: it is possible that a player learns the action of another player before making its choice. Delays of choices are controled by the adversary and each player can only secure the worst-case payoff over the adversary's decisions. In this paper we consider such asynchronous versions of arbitrary two-person strategic games and we study how the presence of the asynchronous adversary influences the behavior of the players, assumed to be selfish but rational. We concentrate on deterministic (pure) strategies, and in particular, on the existence and characteristics of pure Nash equilibria in such games. It turns out that the rational behavior of players changes significantly if the decision process is asynchronous. We show that pure Nash equilibria often exist in the asynchronous version of the game even if there were no such equilibria in the synchronous game. We also show that a mere threat of asynchrony in the game may make social optimum a rational choice while it was not rational in the synchronous game. [ABSTRACT FROM AUTHOR]

A group of mobile robots (beachcombers) have to search collectively every point of a given domain. At any given moment, each robot can be in walking mode or in searching mode. It is assumed that each robot's maximum allowed searching speed is strictly smaller than its maximum allowed walking speed. A point of the domain is searched if at least one of the robots visits it in searching mode. The Beachcombers' Problem consists in developing efficient schedules (algorithms) for the robots which collectively search all the points of the given domain as fast as possible. We consider searching schedules in the following one-dimensional geometric domains: the cycle of a known circumference L , the finite straight line segment of a known length L , and the semi-infinite line [ 0 , + ∞). We first consider the online Beachcombers' Problem (i.e. the scenario when the robots do not know in advance the length of the segment to be searched), where the robots are initially collocated at the origin of a semi-infinite line. It is sought to design a schedule A with maximum speed S , defined as S = inf ℓ ⁡ ℓ t A (ℓ) , where t A (ℓ) denotes the time when the search of the segment [ 0 , ℓ ] is completed under A. We consider a discrete and a continuous version of the problem, depending on whether the infimum is taken over ℓ ∈ N ⁎ or ℓ ≥ 1. We prove that the LeapFrog algorithm, which was proposed in Czyzowicz et al. (2015) [12] , is in fact optimal in the discrete case. This settles in the affirmative a conjecture from that paper. We also show how to extend this result to the more general continuous online setting. For the offline version of the Beachcombers' Problem (i.e. the scenario when the robots know in advance the length of the segment to be searched), we consider the t-source Beachcombers' Problem (i.e. all robots start from a fixed number t ≥ 1 of starting positions) on the cycle and on the finite segment. For the t-source Beachcombers' Problem on the cycle, we show that the structure of the optimal solutions is identical to the structure of the optimal solutions to the 2 t -source Beachcombers' Problem on a finite segment. In consequence, by using results from Czyzowicz et al. (2014) [13] , we prove that the 1-source Beachcombers' Problem on the cycle is NP-hard, and we derive approximation algorithms for the problem. For the t-source variant of the Beachcombers' Problem on the cycle and on the finite segment, we also derive efficient approximation algorithms. One important contribution of our work is that, in all variants of the offline Beachcombers' Problem that we discuss, we allow the robots to change direction of movement and search points of the domain on both sides of their respective starting positions. This represents a significant generalization compared to the model considered in Czyzowicz et al. (2014) [13] , in which each robot had a fixed direction of movement that was specified as part of the solution to the problem. We manage to prove that changes of direction do not help the robots achieve optimality. [ABSTRACT FROM AUTHOR]

Abstract A pair of agents (robots) are moving in a graph with the goal of meeting at the same node or while traversing the same edge. An asynchronous adversary knows the prescribed walks of the two agents and is in complete control of the speed of each agent during its walk. We provide a complete characterization of pairs of walks that enforce rendezvous against an asynchronous adversary after traversing a given number of edges. The characterization is efficient in that it can be checked in polynomial time. We argue that the certificate of rendezvous enforcement that is produced by the checking algorithm contains a wealth of information on why rendezvous is enforced. [ABSTRACT FROM AUTHOR]