Back to Search
Start Over
Hardness and Approximation Results for Black Hole Search in Arbitrary Graphs.
- Source :
- Structural Information & Communication Complexity; 2005, p200-215, 16p
- Publication Year :
- 2005
-
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. We consider the task of locating a black hole in a (partially) synchronous arbitrary network, assuming an upper bound on the time of any edge traversal by an agent. For a given graph and a given starting node we are interested in finding the fastest possible Black Hole Search by two agents (the minimum number of agents capable to identify a black hole). We prove that this problem is NP-hard in arbitrary graphs, thus solving an open problem stated in [2]. We also give a 7/2-approximation algorithm, thus improving on the 4-approximation scheme observed in [2]. Our approach is to explore the given input graph via some spanning tree. Even if it represents a very natural technique, we prove that this approach cannot achieve an approximation ratio better than 3/2. Keywords: approximation algorithm, black hole search, graph exploration, mobile agent, NP-hardness. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISBNs :
- 9783540260523
- Database :
- Supplemental Index
- Journal :
- Structural Information & Communication Complexity
- Publication Type :
- Book
- Accession number :
- 32910264
- Full Text :
- https://doi.org/10.1007/11429647_17