1,720,996 research outputs found
A Quasi-Hole Detection Algorithm for Recognizing k-Distance-Hereditary Graphs, with k < 2
Full text linkCicerone and Di Stefano defined and studied the class of k-distance-hereditary graphs, i.e., graphs where the distance in each connected induced subgraph is at most k times the distance in the whole graph. The defined graphs represent a generalization of the well known distance-hereditary graphs, which actually correspond to 1-distance-hereditary graphs. In this paper we make a step forward in the study of these new graphs by providing characterizations for the class of all the k-distance-hereditary graphs such that k<2. The new characterizations are given in terms of both forbidden subgraphs and cycle-chord properties. Such results also lead to devise a polynomial-time recognition algorithm for this kind of graph that, according to the provided characterizations, simply detects the presence of quasi-holes in any given graph
Breaking Symmetries on Tessellation Graphs via Asynchronous Robots: The Line Formation Problem as a Case Study
Full text linkConcerning the coordination of autonomous mobile robots, the main focus has been on the important class of Pattern Formation problems, where the robots are required to arrange themselves to form a given geometric shape. This class of problems has been extensively studied in the continuous environment (e.g., the Euclidean plane), whereas few results exist when robots move in a discretization of the plane, like infinite grids. In this environment, to form any pattern, the problem of breaking symmetries emerges. Breaking the symmetry by moving some leader robot is not a straightforward task due to the movement restrictions as all the adjacent nodes of the leader may be occupied. It may even happen that before obtaining the requested asymmetric configuration, most of the robots must be moved. Due to the asynchrony of robots, this fact greatly increases the difficulty of the problem. We assume very weak robots moving on any regular tessellation graph as a discretization of the Euclidean plane, and we devise an algorithm able to solve the Symmetry Breaking problem on both the square and triangular grids. It is important to note that is proposed so that it can be used as a module for solving more general problems. As a case study, we use to deal with the Line Formation problem, where robots must arrange themselves to occupy contiguous vertices along a grid line. In this respect, we first provide an algorithm able to partially solve this problem (it works with configurations in which it is not necessary to break symmetries), and then we show how and can be combined to form . We provide a complete characterization of the solvability of the Line Formation problem on the considered topologies by showing that solves the problem in each configuration where this is possible
Breaking symmetries on tessellation graphs via asynchronous robots
Full text linkWe consider the coordination of autonomous mobile robots operating in the standard Look-Compute-Move cycles. Robots are assumed to be very weak computational units, since they are asynchronous, oblivious, anonymous, silent and execute the same distributed algorithm. In this area, the main focus has been on the important class of Pattern Formation problems, where the robots are required to arrange themselves to form a given geometric shape. This class of problems has been extensively studied in the Euclidean plane, whereas few results exist when robots move on a discretization of the plane, like infinite grids. In infinite grids, in order to form any pattern, the problem of breaking symmetries clearly emerges. Breaking the symmetry by moving some leader robot is not a straightforward task due to the movement restrictions as all the adjacent nodes of the leader may be occupied. Due to the asynchrony of robots, this fact greatly increases the difficulty of the problem. We assume regular tessellation graphs as discretization of the Euclidean plane, and we devise an algorithm able to solve the Symmetry Breaking problem on both the square and triangular grids. The algorithm is proposed so that it can be also combined with other modules
Characterizing and computing in linear time mutual-visibility parameters in distance-hereditary graphs
Full text linkThe mutual-visibility problem in a graph G asks for the cardinality of a largest set of vertices X⊆V(G) so that for any two vertices x,y∈X there is a shortest x,y-path whose internal vertices are all not in X. Variations of this problem are known, based on the extension of the visibility property of vertices that are in and/or outside X. It is known that solving the mutual-visibility problem in all its variations is NP-complete, whereas it has been shown that there are exact formulas for special graph classes like paths, cycles, blocks, cographs, and for the Cartesian product of some simple graphs like paths, cliques and cycles. In this paper, we study the (variations of) mutual-visibility problem in the context of distance-hereditary graphs. In particular, we introduce the direct canonical decomposition of a graph as a tool for defining useful structural properties of the graphs studied. Then, we show that such properties allow us to devise a linear-time algorithm for solving all the variants of the mutual-visibility problem for distance-hereditary graphs. In turn, this allowed us to show that a recently posed conjecture about the total mutual-visibility number of distance-hereditary graphs holds
A structured methodology for designing distributed algorithms for mobile entities
No full textFollowing the wide investigation in distributed computing issues by mobile entities of the last two decades, we consider the need of a structured methodology to tackle the arisen problems. The aim is to simplify both the design of the resolution algorithms and the writing of the required correctness proofs. We would encourage the usage of a common framework in order to help both algorithm designers and reviewers in the intricate work of delivering and analyzing the proposed resolution strategies. We demonstrate the effectiveness and usefulness of the new methodology by highlighting various peculiarities arising in different scenarios. In particular, we consider two different tasks for asynchronous entities moving in the Euclidean plane and in graphs, respectively. We show how two resolution strategies have been designed by following the accurate guide dictated by the methodology. Furthermore, we also show how the corresponding correctness proofs are obtained
Mutual-visibility in distance-hereditary graphs: A linear-time algorithm
No full textThe concept of mutual-visibility in graphs has been recently introduced. If X is a subset of vertices of a graph G, then vertices u and v are X-visible if there exists a shortest u, v-path P such that V(P) ∩ X ⊆ {u, v}. If every two vertices from X are X-visible, then X is a mutual-visibility set. The mutual-visibility number of G is the cardinality of a largest mutual-visibility set of G. It is known that computing the mutual-visibility number of a graph is NP-complete, whereas it has been shown that there are exact formulas for special graph classes like paths, cycles, blocks, cographs, and grids. In this paper, we study the mutual-visibility in distance-hereditary graphs and show that the mutual-visibility number can be computed in linear time for this class
“Semi-Asynchronous”: a new scheduler in distributed computing
Full text linkThe study of mobile entities that based on local information have to accomplish global tasks is of main interest for the scientific community. Classic models for the activation and synchronization of mobile entities are the fully-synchronous (FSYNC), semi-synchronous (SSYNC), and asynchronous (ASYNC) models, where entities alternate between active and inactive states with different timing. According to the assumed synchronization model, very different results have been achieved in the field of distributed computing. One of the main outcomes is the big gap between the ASYNC and the other models in terms of manageability and algorithm design. In fact, there are still many problems for which it is not known whether synchronicity is crucial for designing resolution algorithms or not. In order to better understand the ASYNC case, here we propose a further model referred to as the semi-asynchronous (SASYNC). This slightly deviates from SSYNC. In fact, like in SSYNC (and FSYNC), the duration of the activation of an entity is kept of fixed time whereas, like in ASYNC, the starting instant of the activation is not fully synchronized with the possible activation of other entities. We show that for entities moving on graphs, the SSYNC model allows accomplishing more tasks than the SASYNC that in turn allows accomplishing more tasks than the ASYNC. Furthermore, our results show that, especially to tackle problems in the Euclidean plane, the SASYNC model is already quite challenging, therefore there is no need to get involved with complications arising in the ASYNC model
Solving the Pattern Formation by Mobile Robots with Chirality
Full text linkAmong fundamental problems in the context of distributed computing by mobile robots, the Pattern Formation (PF) is certainly the most representative. Given a multi-set F of points in the Euclidean plane and a set R of robots such that |R|=|F|, PF asks for a distributed algorithm that moves robots so as to reach a configuration similar to F. Similarity means that robots must be disposed as F regardless of translations, rotations, reflections, uniform scalings. In Fujinaga et al. SIAM J. Comput., 2015, PF has been approached by assuming asynchronous robots endowed with chirality, i.e. a common handedness. The proposed algorithm along with its correctness proof turned out to be flawed. In this paper, we propose a new algorithm on the basis of a recent methodology studied for approaching problems in the context of distributed computing by mobile robots. According to this methodology, the correctness proof results to be well-structured and less prone to faulty arguments. We then ultimately characterize PF when chirality is assumed
Gathering robots in graphs: The central role of synchronicity
Full text linkThe Gathering task for k robots disposed on the n vertices of a graph G requires robots to move toward a common vertex from where they do not move anymore. When dealing with very weak robots in terms of capabilities, considering synchronous or asynchronous settings may heavily affect the feasibility of the problem. In fact, even though dealing with asynchronous robots in general requires more sophisticated strategies with respect to the synchronous counterpart, sometimes it comes out that asynchronous robots simply cannot solve the problem whereas synchronous robots can. We study general properties of graphs that can be exploited in order to accomplish the gathering task in the synchronous setting, obtaining an interesting and innovative sufficient condition for the feasibility of the gathering task in graphs, regardless the topology. Furthermore, we consider dense and symmetric graphs like complete and complete bipartite graphs where in general the topology does not allow to distinguish vertices where to finalize the gathering. In such topologies, we fully characterize the solvability of the gathering task in the synchronous setting by suitably combining some strategies arising from the general approach with specific techniques dictated by the considered topologies. From the lower bound point of view in terms of number of synchronous time units required to accomplish the gathering task, in general nothing better than Ω(DG), with DG being the diameter of the input graph G, can be provided. For both complete and complete bipartite graphs, we prove a lower bound of Ω(logφk), with φ being the well-known golden ratio. Combined with the provided algorithms, this reveals to be asymptotically tight for complete graphs while for complete bipartite graphs an additive factor of δ(k) is achieved, with δ(k) being the function that returns the number of divisors of the integer k
- …
