تقرير
Black Hole Search in Dynamic Cactus Graph
العنوان: | Black Hole Search in Dynamic Cactus Graph |
---|---|
المؤلفون: | Bhattacharya, Adri, Italiano, Giuseppe F., Mandal, Partha Sarathi |
سنة النشر: | 2023 |
المجموعة: | Computer Science |
مصطلحات موضوعية: | Computer Science - Distributed, Parallel, and Cluster Computing |
الوصف: | 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 |
نوع الوثيقة: | Working Paper |
URL الوصول: | http://arxiv.org/abs/2311.10984 |
رقم الأكسشن: | edsarx.2311.10984 |
قاعدة البيانات: | arXiv |
الوصف غير متاح. |