





















In this paper, we address the challenge of locating a black hole within a dynamic graph using a set of scattered agents, which start from arbitrary positions in the graph. A black hole is defined as a node that silently eliminates any agent that visits it, effectively modeling network failures such as a crashed host or a destructive virus. The black hole search problem is considered solved when at least one agent survives and possesses a complete map of the graph, including the precise location of the black hole. Our study focuses on the scenario where the underlying graph is a dynamic 1-interval connected ring: a ring graph where, in each round, one edge may be absent. Agents communicate with other agents using movable pebbles that can be placed on nodes. In this setting, we demonstrate that three agents are sufficient to identify the black hole in $O(n^2)$ moves. Furthermore, we prove that this number of agents is optimal. Additionally, we establish that the complexity bound is tight, requiring $Ω(n^2)$ moves for any algorithm solving the problem with three agents, even when stronger communication mechanisms, such as unlimited-size whiteboards on nodes, are available.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。