Search

Distance labeling schemes are schemes that label the vertices of a graph with short labels in such a way that the distance between any two vertices u and v can be determined efficiently by merely inspecting the labels of u and v, without using any other information. Similarly, routing labeling schemes label the vertices of a graph in a such a way that given the labels of a source node and a destination node, it is possible to compute efficiently the port number of the edge from the source that heads in the direction of the destination. One of important problems is finding natural classes of graphs admitting distance and/or routing labeling schemes with labels of polylogarithmic size. In this paper, we show that the class of cube-free median graphs on n nodes enjoys distance and routing labeling schemes with labels of O (log 3 n) bits. [ABSTRACT FROM AUTHOR]

In this paper, we extend two classical results about the density of subgraphs of hypercubes to subgraphs G of Cartesian products G1□⋯□Gm of arbitrary connected graphs. Namely, we show that (∣E(G)|/∣V(G)∣)≤⌈2max{dens(G1),...,dens(Gm)}⌉log∣V(G)∣, where dens(H) is the maximum ratio ∣E(H′)∣/∣V(H′)∣ taken over all subgraphs H′ of H. We introduce the notions of VC‐dimension VC‐dim⁡(G) and VC‐density VC‐dens(G) of a subgraph G of a Cartesian product G1□⋯□Gm, generalizing the classical Vapnik‐Chervonenkis dimension of set‐families (viewed as subgraphs of hypercubes). We prove that if G1,...,Gm belong to the class G(H) of all finite connected graphs not containing a given graph H as a minor, then for any subgraph G of G1□⋯□Gm the sharper inequality (∣E(G)∣/∣V(G)∣)≤μ(H)⋅VC‐dim⁡*(G) holds, where μ(H) is the supremum of the densities of the graphs from G(H). We refine and sharpen these two results to several specific graph classes. We also derive upper bounds (some of them polylogarithmic) for the size of adjacency labeling schemes of subgraphs of Cartesian products. [ABSTRACT FROM AUTHOR]

Let S be a family of subsets of a set X of cardinality m and VC-dim (S) be the Vapnik–Chervonenkis dimension of S. Haussler et al. (1994) proved that if G 1 (S) = (V , E) is the subgraph of the hypercube Q m induced by S (called the 1-inclusion graph of S), then | E | | V | ≤ VC-dim (S). Haussler (1995) presented an elegant proof of this inequality using the shifting operation. In this note, we adapt the shifting technique to prove that if S is an arbitrary set family and G 1 , 2 (S) = (V , E) is the 1,2-inclusion graph of S (i.e., the subgraph of the square Q m 2 of the hypercube Q m induced by S), then | E | | V | ≤ d 2 , where d ≔ cVC-dim ∗ (S) is the clique-VC-dimension of S (which we introduce in this paper). The 1,2-inclusion graphs are exactly the subgraphs of halved cubes and comprise subgraphs of Johnson graphs as a subclass. [ABSTRACT FROM AUTHOR]

k -Approximate distance labeling schemes are schemes that label the vertices of a graph with short labels in such a way that the k -approximation of the distance between any two vertices u and v can be determined efficiently by merely inspecting the labels of u and v , without using any other information. One of the important problems is finding natural classes of graphs admitting exact or approximate distance labeling schemes with labels of polylogarithmic size. In this paper, we describe a 4-approximate distance labeling scheme for the class of K 4 -free bridged graphs. This scheme uses labels of poly-logarithmic length O (log ⁡ n 3) allowing a constant decoding time. Given the labels of two vertices u and v , the decoding function returns a value between the exact distance d G (u , v) and its quadruple 4 d G (u , v). [ABSTRACT FROM AUTHOR]

Abstract: A mobile robot, represented by a point moving along a polygonal line in the plane, has to explore an unknown polygon and return to the starting point. The robot has a sensing area which can be a circle or a square centered at the robot. This area shifts while the robot moves inside the polygon, and at each point of its trajectory the robot “sees” (explores) all points for which the segment between the robot and the point is contained in the polygon and in the sensing area. We focus on two tasks: exploring the entire polygon and exploring only its boundary. We consider several scenarios: both shapes of the sensing area and the Manhattan and the Euclidean metrics. We focus on two quality benchmarks for exploration performance: optimality (the length of the trajectory of the robot is equal to that of the optimal robot knowing the polygon) and competitiveness (the length of the trajectory of the robot is at most a constant multiple of that of the optimal robot knowing the polygon). Most of our results concern rectilinear polygons. We show that optimal exploration is possible in only one scenario, that of exploring the boundary by a robot with square sensing area, starting at the boundary and using the Manhattan metric. For this case we give an optimal exploration algorithm, and in all other scenarios we prove impossibility of optimal exploration. For competitiveness the situation is more optimistic: we show a competitive exploration algorithm for rectilinear polygons whenever the sensing area is a square, for both tasks, regardless of the metric and of the starting point. Finally, we show a competitive exploration algorithm for arbitrary convex polygons, for both shapes of the sensing area, regardless of the metric and of the starting point. [Copyright &y& Elsevier]

Two mobile agents, starting from different nodes of an unknown network, have to meet at a node. Agents move in synchronous rounds using a deterministic algorithm. Each agent has a different label, which it can use in the execution of the algorithm, but it does not know the label of the other agent. Agents do not know any bound on the size of the network. In each round an agent decides if it remains idle or if it wants to move to one of the adjacent nodes. Agents are subject to delay faults: if an agent incurs a fault in a given round, it remains in the current node, regardless of its decision. If it planned to move and the fault happened, the agent is aware of it. We consider three scenarios of fault distribution: random (independently in each round and for each agent with constant probability $$0

Abstract: We study the problem of locating a particularly dangerous node, the so-called black hole in a synchronous anonymous ring network with mobile agents. A black hole is a harmful stationary process residing in a node of the network and destroying all mobile agents visiting that node without leaving any trace. Unlike most previous research on the black hole search problem which employed a co-located team of agents, we consider the more challenging scenario when the agents are identical and initially scattered within the network. Moreover, we solve the problem with agents that have constant-sized memory and carry a constant number of identical tokens, which can be placed at nodes of the network. In contrast, the only known solutions for the case of scattered agents searching for a black hole, use stronger models where the agents have non-constant memory, can write messages in whiteboards located at nodes or are allowed to mark both the edges and nodes of the network with tokens. This paper solves the problem for ring networks containing a single black hole. We are interested in the minimum resources (number of agents and tokens) necessary for locating all links incident to the black hole. We present deterministic algorithms for ring topologies and provide matching lower and upper bounds for the number of agents and the number of tokens required for deterministic solutions to the black hole search problem, in oriented or unoriented rings, using movable or unmovable tokens. [Copyright &y& Elsevier]

Abstract: 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 is 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 , 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. [Copyright &y& Elsevier]

Abstract: 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 they meet. 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. [Copyright &y& Elsevier]

We consider the problem of collectively delivering a package from a specified source to a designated target location in a graph, using multiple mobile agents. Each agent starts from some vertex of the graph; it can move along the edges of the graph and can pick up the package from a vertex and drop it in another vertex during the course of its movement. However, each agent has limited energy budget allowing it to traverse a path of bounded length B ; thus, multiple agents need to collaborate to move the package to its destination. Given the positions of the agents in the graph and their energy budgets, the problem of finding a feasible movement schedule is called the Collaborative Delivery problem and has been studied before. One of the open questions from previous results is what happens when the delivery must follow a fixed path given in advance. Although this special constraint reduces the search space for feasible solutions, the problem remains NP hard, as the general version of the problem. We consider the optimization version of the problem that asks for the optimal energy budget B per agent which allows for a feasible delivery schedule along a fixed path, given the initial positions of the agents. We provide polynomial time approximation algorithms for both directed and undirected graphs, and establish hardness of approximation for the directed case. Note that the fixed path version of collaborative delivery requires completely different techniques since a single agent may be used multiple times, unlike the general version of collaborative delivery studied before. We show that restricting each agent to a single pickup allows better approximations for fixed path collaborative delivery compared to the original problem. Finally, we provide a polynomial time algorithm for determining a feasible delivery strategy, if any exists, for a given budget B when the number of available agents is bounded by a constant. [ABSTRACT FROM AUTHOR]

We consider the problem of collectively delivering some package from a specified source to a designated target location in a graph, using multiple mobile agents. Each agent has limited energy which constrains the distance it can move. Hence multiple agents need to collaborate to move the package, each agent handing over the package to the next agent to carry it forward. Given the positions of the agents in the graph and their respective budgets, the problem of finding a feasible movement schedule for the agents can be challenging. We consider two variants of the problem: in non-returning delivery, the agents can stop anywhere; whereas in returning delivery, each agent needs to return to its starting location, a variant which has not been studied before. We first provide a polynomial-time algorithm for returning delivery on trees, which is in contrast to the known (weak) NP-hardness of the non-returning version. In addition, we give resource-augmented algorithms for returning delivery in general graphs. Finally, we give tight lower bounds on the required resource augmentation for both variants of the problem. In this sense, our results close the gap left by previous research. [ABSTRACT FROM AUTHOR]

A collection of k mobile robots, initially placed at the origin of the plane, are searching for a stationary target. Each robot r i has a unit visibility range and can move no faster than its maximal speed v i , for i = 1 , 2 ,... , k. The robots can communicate between themselves. We consider two communication models: wireless, in which a message sent by a robot can reach all other robots immediately, regardless of their positions, and face-to-face (F2F), in which robots can only exchange information when they are meeting. We assume that up to f robots, where f < k , may be unreliable. We consider two models of unreliability: (1) crash faults, in which we deal with an absence of some of the robots' capabilities (communication, perception, motion, etc.), and (2) byzantine faults, in which the robots may be malicious in that they may execute a wrong algorithm (e.g., transmitting wrong information). The goal is to minimize the group search time, which is equal to the time of arrival to the target of the last reliable robot. This is expressed as a function of d , the distance from the origin to the target. Our proposed algorithms for crash faults are asymptotically optimal in d in both communication models. For byzantine faults, our algorithm is asymptotically optimal for the wireless model. In the F2F model, we propose two algorithms: the first one has a competitive ratio of 2, while the second algorithm works for k ≥ 2 f + 2 and is optimal when the robots speeds are all equal. [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]

A set of identical, mobile agents is deployed in a weighted network. Each agent has a battery-a power source allowing it to move along network edges. An agent uses its battery proportionally to the distance traveled. We consider two tasks: convergecast, in which at the beginning, each agent has some initial piece of information, and information of all agents has to be collected by some agent; and broadcast in which information of one specified agent has to be made available to all other agents. In both tasks, the agents exchange the currently possessed information when they meet. The objective of this paper is to investigate what is the minimal value of power, initially available to all agents, so that convergecast or broadcast can be achieved. We study this question in the centralized and the distributed settings. In the centralized setting, there is a central monitor that schedules the moves of all agents. In the distributed setting every agent has to perform an algorithm being unaware of the network. In the centralized setting, we give a linear-time algorithm to compute the optimal battery power and the strategy using it, both for convergecast and for broadcast, when agents are on the line. We also show that finding the optimal battery power for convergecast or for broadcast is NP-hard for the class of trees. On the other hand, we give a polynomial algorithm that finds a 2-approximation for convergecast and a 4-approximation for broadcast, for arbitrary graphs.In the distributed setting, we give a 2-competitive algorithm for convergecast in trees and a 4-competitive algorithm for broadcast in trees. The competitive ratio of 2 is proved to be the best for the problem of convergecast, even if we only consider line networks. Indeed, we show that there is no ( $$2-\epsilon $$ )-competitive algorithm for convergecast or for broadcast in the class of lines, for any $$\epsilon >0$$ . [ABSTRACT FROM AUTHOR]

In this article, we characterize the graphs G that are the retracts of Cartesian products of chordal graphs. We show that they are exactly the weakly modular graphs that do not contain K2, 3, the 4-wheel minus one spoke [ABSTRACT FROM AUTHOR]