Black Hole Search by Scattered Agents on Time-Varying Dynamic Graphs
摘要
A black hole is a malicious node in a graph that destroys resources entering into it without leaving any trace. The problem of Black Hole Search (BHS) using mobile agents requires that at least one agent survive and terminate after locating the black hole. Recently, this problem is studied on 1-bounded 1-interval connected dynamic graphs, where there is a footprint graph, and at most one edge can disappear from the footprint in a round, provided that the graph remains connected. In this setting, the authors proposed an algorithm that solves the BHS problem when all agents start from a single node (rooted initial configuration). They also proved that at least \(2\delta _{BH} + 1\) agents are necessary to solve the problem when agents are initially placed arbitrarily across the nodes of the graph (scattered initial configuration), where \(\delta _{BH}\) denotes the degree of the black hole. In this work, we present an algorithm that solves the BHS problem using \(2\delta _{BH} + 17\) many initially scattered agents. Our result matches asymptotically with the existing rooted algorithm under the same model assumptions.