Search

A mobile agent navigating along edges of a simple connected unweighted graph, either finite or countably infinite, has to find an inert target (treasure) hidden in one of the nodes. This task is known as treasure hunt. The agent has no a priori knowledge of the graph, of the location of the treasure, or of the initial distance to it. The cost of a treasure hunt algorithm is the worst-case number of edge traversals performed by the agent until finding the treasure. Awerbuch et al. [3] considered graph exploration and treasure hunt for finite graphs in a restricted model where the agent has a fuel tank that can be replenished only at the starting node s. The size of the tank is B = 2(1 + a)r, for some positive real constant a, where r, called the radius of the graph, is the maximum distance from s to any other node. The tank of size B allows the agent to make at most -B° edge traversals between two consecutive visits at node s. Let e (d) be the number of edges whose at least one endpoint is at distance less than d from s. Awerbuch et al. [3] conjectured that it is impossible to find a treasure hidden in a node at distance at most d at cost nearly linear in e (d). We first design a deterministic treasure hunt algorithm working in the model without any restrictions on the moves of the agent at cost O(e (d) logd) and then show how to modify this algorithm to work in the model from Awerbuch et al. [3] with the same complexity. Thus, we refute the preceding 20-year-old conjecture. We observe that no treasure hunt algorithm can beat cost T(e (d)) for all graphs, and thus our algorithms are also almost optimal. [ABSTRACT FROM AUTHOR]

Treasure hunt is finding a hidden inert target by a mobile agent. We consider deterministic algorithms for treasure hunt in trees. Our goal is to establish the impact of different kinds of initial knowledge given to the agent on the cost of treasure hunt, defined as the total number of edge traversals until the agent reaches the treasure. The agent can be initially given either a complete map of the tree rooted at its starting node, with all port numbers marked, or a blind map of the tree rooted at its starting node but without port numbers. It may also be given, or not, the distance from the root to the treasure. This yields four different knowledge types that are partially ordered by their precision. The penalty of a less precise knowledge type 풯2 over a more precise knowledge type 풯1 measures intuitively the worst‐case ratio of the cost of an algorithm supplied with knowledge of type 풯2 over the cost of an algorithm supplied with knowledge of type 풯1. Our main results establish penalties for comparable knowledge types in this partial order. For knowledge types with known distance, the penalty for having a blind map over a complete map turns out to be very large. By contrast, for unknown distance, the penalty of having a blind map over having a complete map is small. When a map is provided (either complete or blind), the penalty of not knowing the distance over knowing it is medium. [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]

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]

Two mobile agents (robots) with distinct labels have to meet in an arbitrary, possibly infinite, unknown connected graph or in an unknown connected terrain in the plane. Agents are modeled as points, and the route of each of them only depends on its label and on the unknown environment. The actual walk of each agent also depends on an asynchronous adversary that may arbitrarily vary the speed of the agent, stop it, or even move it back and forth, as long as the walk of the agent is continuous, does not leave its route and covers all of it. Meeting in a graph means that both agents must be at the same time in some node or in some point inside an edge of the graph, while meeting in a terrain means that both agents must be at the same time in some point of the terrain. Does there exist a deterministic algorithm that allows any two agents to meet in any unknown environment in spite of this very powerful adversary? We give deterministic rendezvous algorithms for agents starting at arbitrary nodes of any anonymous connected graph (finite or infinite) and for agents starting at any interior points with rational coordinates in any closed region of the plane with path-connected interior. In the geometric scenario agents may have different compasses and different units of length. While our algorithms work in a very general setting - agents can, indeed, meet almost everywhere - we show that none of these few limitations imposed on the environment can be removed. On the other hand, our algorithm also guarantees the following approximate rendezvous for agents starting at arbitrary interior points of a terrain as previously stated agents will eventually get to within an arbitrarily small positive distance from each other. [ABSTRACT FROM AUTHOR]

Abstract: For a family of geometric objects in the plane, define as the least integer ℓ such that the elements of can be colored with ℓ colors, in such a way that any two intersecting objects have distinct colors. When is a set of Jordan regions that may only intersect on their boundaries, and such that any point of the plane is contained in at most k regions, it can be proven that since the problem is equivalent to cyclic coloring of plane graphs [O. Amini, L. Esperet, and J. van den Heuvel, A Unified Approach to Distance-Two Colouring of Planar Graphs, In: Proc. 20th Ann. ACM-SIAM Symposium on Discrete Algorithms (SODA09), ACM Press, New-York (2009)]. In this paper, we study the same problem when Jordan regions are replaced by Jordan curves that do not cross (two curves are only allowed to “touch” each other). We conjecture that also in this case, is bounded by ck for some . To support this conjecture, we prove it when the curves are x-monotone (any vertical line intersect each curve at most once), and we give a bound in the general case that also depends on how many times two curves intersect. [Copyright &y& Elsevier]

Abstract: For a family of graphs, a graph U is said to be -universal if every graph of is a subgraph of U. Similarly, a graph is said to be -induced-universal if every graph of is an induced subgraph of U. In this paper, we give constructive proofs of new upper bounds for size and order of such minimal graphs for the family of graphs with no K-minor and more particularly on graphs of bounded treewidth. [Copyright &y& Elsevier]

Abstract: In this paper, we propose an efficient implicit representation of caterpillar and bounded degree trees of n vertices. Our scheme, called Traversal & Jumping, assigns to the n vertices of any bounded degree tree distinct binary labels of bits in time such that we can compute adjacency between two vertices only from their labels. We use our result to improve previous known upper bound for size of labels of implicit representation of outerplanar graphs (respectively planar graphs) to (respectively ()). [Copyright &y& Elsevier]

Abstract: In this paper we give a linear algorithm to edge partition a toroidal graph, i.e., graph that can be embedded on the orientable surface of genus one without edge crossing, into three forests plus a set of at most three edges. For triangulated toroidal graphs, this algorithm gives a linear algorithm for finding three edge-disjoint spanning trees. This is in a certain way an extension of the well-known algorithm of Schnyder''s decomposition for planar graph. [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]