When Agents are Powerful: Black Hole Search in Time-Varying Graphs
摘要
A black hole is a harmful node in a graph that destroys any resource entering it, making its identification a critical task. In the Black Hole Search (BHS) problem, a team of agents operates on a graph G with the objective that at least one agent must survive and correctly identify an edge incident to the black hole. Prior work has addressed BHS in arbitrary dynamic graphs under the restrictive face-to-face communication, where agents can exchange information only when co-located. In this work, we strengthen the capabilities of agents in two ways: (i) global communication, and (ii) 1-hop visibility. These enhancements lead to more efficient solutions for the BHS problem in dynamic graphs.