Hardness and approximation results for Black Hole Search in arbitrary networks

作     者：Klasing, Ralf Markou, Euripides Radzik, Tomasz Sarracco, Fabiano 

作者机构：Univ Bordeaux 1 LaBRI CNRS F-33405 Talence France McMaster Univ Sch Computat Engn & Sci Hamilton ON L8S 4K1 Canada Kings Coll London Dept Comp Sci London WC2R 2LS England Sapienza Univ Roma Dipartimento Informat & Sistemist CTL Ctr Ric Transporto & Logist Rome Italy 

出 版 物：《THEORETICAL COMPUTER SCIENCE》 (理论计算机科学)

年 卷 期：2007年第384卷第2-3期

页      面：201-221页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：Ambassade de France en Grèce Institut Franc¸ais d’Athènes, (EPEAEK 70/3/6865) Royal Society, (ESEP 16244) 

主　　题：approximation algorithm Black Hole Search graph exploration mobile agent NP-hardness 

摘      要：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 by exploring it with mobile agents. We consider the problem of designing the fastest Black Hole Search, given the map of the network and the starting node. 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 NP-hard in arbitrary graphs (even in planar graphs), solving an open problem stated in [J. Czyzowicz, D. Kowalski, E. Markou, A. Pelc, Searching for a black hole in tree networks, in: Proc. 8th Int. Conf. on Principles of Distributed Systems, OPODIS 2004, 2004, pp. 34-35. Also: Springer LNCS, vol. 33/8-approximation algorithm, showing the first non-trivial approximation ratio upper bound for this pp. 67-801, We also give a 3 3 problem. Our algorithm follows a natural approach of exploring networks via spanning trees. We prove that this approach cannot lead to an approximation ratio bound better than 3/2. (C) 2007 Elsevier B.V. All rights reserved.