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