Explore and repair graphs with black holes using mobile entities

Autor: Daniele Frigioni, Mattia D'Emidio, Alfredo Navarra
Rok vydání: 2015
Předmět:
Zdroj: Theoretical Computer Science. 605:129-145
ISSN: 0304-3975
DOI: 10.1016/j.tcs.2015.09.002
Popis: In this paper, we study the problem of mobile entities that synchronously have to explore and repair a graph with faulty nodes, usually called black-holes, that destroy any entering entity. We consider the scenario where the destruction of an entity by means of a black-hole also affects all the entities within a fixed range r (in terms of number of edges), while the black-hole disappears. Clearly, if there are b black-holes in the graph, then k � b entities are necessary to remove all of them from that graph. We ask for the minimum number of synchronous steps needed to make safe all the graph.The results of this paper are both theoretical and experimental, and can be summarized as follows. From the theoretical point of view, first we show that the problem is NP-hard even for b = k = 1 . Then, we provide a general lower bound holding when r � 0 and a higher one for the case of r 0 . We then consider the case of r � 1 . We propose an optimal solution holding when k is unbounded, that is, an infinite number of robots is available. Then, we provide three different exploration strategies, named snake, scout, and parallel-scout, respectively, for the case of bounded k, that is, the number of robots is fixed a priori. The three strategies are then analyzed according to the time complexity with respect to the lower bound. From the experimental point of view, we implemented the three strategies and tested them on different scenarios with the aim of assessing their practical performance. The experiments confirm the theoretical analysis and show that parallel-scout is always by far the best exploration strategy in practice.
Databáze: OpenAIRE
Externí odkaz: