Metraipolis › archive › dc_dba886e61512

Don't Be Afraid to Die: Black Hole Search in Dynamic Graphs with Fewer Agents — arXiv:2609.06850

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.06850
License (as archived)
CC0-1.0
Archived
2026-10-16T13:07:13.313Z
SHA-256 of the archived text
ccea9d7052ccd479e0a59b292ada847d079acd956b5e870c7e52b99e06b50406
Stable URL of this page
https://metraipolis.com/documento/dc_dba886e61512

How to cite

Don't Be Afraid to Die: Black Hole Search in Dynamic Graphs with Fewer Agents — arXiv:2609.06850 — arXiv (en), https://arxiv.org/abs/2609.06850 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_dba886e61512 (Metraipolis archive dc_dba886e61512, sha256 ccea9d7052ccd479e0a59b292ada847d079acd956b5e870c7e52b99e06b50406)
BibTeX
@misc{dcdba886e61512,
  title = {Don't Be Afraid to Die: Black Hole Search in Dynamic Graphs with Fewer Agents — arXiv:2609.06850},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.06850},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_dba886e61512; sha256 ccea9d7052ccd479e0a59b292ada847d079acd956b5e870c7e52b99e06b50406},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.06850. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

We consider a team of synchronous mobile agents operating in a port-labeled network. There is one node in the network, called a black hole, that permanently destroys any agent that visits the node. The team of agents must safely locate the black hole, i.e., at least one agent must survive, terminate its algorithm at a node adjacent to the black hole, and output the port number that leads to the black hole from its current position. In the setting where the network is a 1-bounded 1-interval connected dynamic graph, Kaur et al. (SSS 2025) showed that a team consisting of $2\delta_{BH}+17$ agents is sufficient to solve the task from a scattered configuration, where $\delta_{BH}$ denotes the degree of the black hole node. We show that $2\delta_{BH}+3$ agents are sufficient, nearly matching the $2\delta_{BH}+1$ lower bound provided in Kaur et al. (ICDCN 2025).

Tema degli esploratori: calcolo e infrastrutture (retro-catalogo arXiv: annunci del 2026-09-09 in cs.DC).
Categorie arXiv: Distributed, Parallel, and Cluster Computing (cs.DC) ; Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2609.06850 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-16T13:02:21.567Z dalla pagina https://arxiv.org/catchup/cs.DC/2026-09-09?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).