arXiv preprint ·
Don't Be Afraid to Die: Black Hole Search in Dynamic Graphs with Fewer Agents
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
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δ_{BH}+17$ agents is sufficient to solve the task from a scattered configuration, where $δ_{BH}$ denotes the degree of the black hole node. We show that $2δ_{BH}+3$ agents are sufficient, nearly matching the $2δ_{BH}+1$ lower bound provided in Kaur et al. (ICDCN 2025).
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Distributed & Parallel Computing
Phase-cycled randomized benchmarking of quantum processors: recovering hidden classical noise correlations
Online Draft Co-Training for Speculative Decoding in Large-Scale, Long-Context RL Post-Training
PACO: A Fully Cache-Oblivious Parallel FFT with One Global Redistribution
Robust Decentralized Federated Distillation via Multi-Modality Knowledge Collaboration
EStream: Fast and Memory-Efficient MoE Prefill through Expert Virtualization on Mobile NPUs
Get the few papers worth your time in Distributed & Parallel Computing every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.