Black Hole Search in Dynamic Cactus Graph
| Autor: | Bhattacharya, Adri, Italiano, Giuseppe F., Mandal, Partha Sarathi |
|---|---|
| Rok vydání: | 2023 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | We study the problem of black hole search by a set of mobile agents, where the underlying graph is a dynamic cactus. A black hole is a dangerous vertex in the graph that eliminates any visiting agent without leaving any trace behind. Key parameters that dictate the complexity of finding the black hole include: the number of agents required (termed as \textit{size}), the number of moves performed by the agents in order to determine the black hole location (termed as \textit{move}) and the \textit{time} (or round) taken to terminate. This problem has already been studied where the underlying graph is a dynamic ring \cite{di2021black}. In this paper, we extend the same problem to a dynamic cactus. We introduce two categories of dynamicity, but still the underlying graph needs to be connected: first, we examine the scenario where, at most, one dynamic edge can disappear or reappear at any round. Secondly, we consider the problem for at most $k$ dynamic edges. In both scenarios, we establish lower and upper bounds for the necessary number of agents, moves and rounds. Comment: This paper recently got accepted in WALCOM 2024 |
| Databáze: | arXiv |
| Externí odkaz: |
|