HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Reports

Approximation bounds for Black Hole Search problems

Abstract : A black hole is a highly harmful stationary process residing in a node of a network and destroying all mobile agents visiting the node without leaving any trace. The Black Hole Search is the task of locating all black holes in a network, through the exploration of its nodes by a set of mobile agents. In this paper we consider the problem of designing the fastest Black Hole Search, given the map of the network, the starting node and a subset of nodes of the network initially known to be safe. We study the version of this problem that assumes that there is at most one black hole in the network and there are two agents, which move in synchronized steps. We prove that this problem is not polynomial-time approximable within any constant factor less than 389/388 (unless PTIME=NPTIME). We give a 6-approximation algorithm, thus improving on the 9.3-approximation algorithm from [3]. We also prove APX-hardness for a restricted version of the problem, in which only the starting node is initially known to be safe.
Complete list of metadata

Cited literature [14 references]  Display  Hide  Download

https://hal.inria.fr/inria-00145157
Contributor : Rapport de Recherche Inria Connect in order to contact the contributor
Submitted on : Wednesday, May 9, 2007 - 12:18:44 PM
Last modification on : Friday, February 4, 2022 - 3:24:52 AM
Long-term archiving on: : Tuesday, September 21, 2010 - 1:09:22 PM

Files

RR-6185.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00145157, version 2

Collections

Citation

Ralf Klasing, Euripides Markou, Tomasz Radzik, Fabiano Sarracco. Approximation bounds for Black Hole Search problems. [Research Report] RR-6185, INRIA. 2007. ⟨inria-00145157v2⟩

Share

Metrics

Record views

216

Files downloads

234