A black hole is a malicious node in a graph that destroys resources entering into it without leaving any trace. The problem of Black Hole Search (BHS) using mobile agents requires that at least one agent survive and terminate after locating the black hole. Recently, this problem is studied on 1-bounded 1-interval connected dynamic graphs, where there is a footprint graph, and at most one edge can disappear from the footprint in a round, provided that the graph remains connected. In this setting, the authors proposed an algorithm that solves the BHS problem when all agents start from a single node (rooted initial configuration). They also proved that at least \(2\delta _{BH} + 1\) agents are necessary to solve the problem when agents are initially placed arbitrarily across the nodes of the graph (scattered initial configuration), where \(\delta _{BH}\) denotes the degree of the black hole. In this work, we present an algorithm that solves the BHS problem using \(2\delta _{BH} + 17\) many initially scattered agents. Our result matches asymptotically with the existing rooted algorithm under the same model assumptions.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Black Hole Search by Scattered Agents on Time-Varying Dynamic Graphs

  • Tanvir Kaur,
  • Ashish Saxena,
  • Partha Sarathi Mandal,
  • Kaushik Mondal

摘要

A black hole is a malicious node in a graph that destroys resources entering into it without leaving any trace. The problem of Black Hole Search (BHS) using mobile agents requires that at least one agent survive and terminate after locating the black hole. Recently, this problem is studied on 1-bounded 1-interval connected dynamic graphs, where there is a footprint graph, and at most one edge can disappear from the footprint in a round, provided that the graph remains connected. In this setting, the authors proposed an algorithm that solves the BHS problem when all agents start from a single node (rooted initial configuration). They also proved that at least \(2\delta _{BH} + 1\) agents are necessary to solve the problem when agents are initially placed arbitrarily across the nodes of the graph (scattered initial configuration), where \(\delta _{BH}\) denotes the degree of the black hole. In this work, we present an algorithm that solves the BHS problem using \(2\delta _{BH} + 17\) many initially scattered agents. Our result matches asymptotically with the existing rooted algorithm under the same model assumptions.