Explore and repair graphs with black holes using mobile entities

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.