{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,3]],"date-time":"2026-06-03T09:59:52Z","timestamp":1780480792261,"version":"3.54.1"},"reference-count":11,"publisher":"Cambridge University Press (CUP)","issue":"4","license":[{"start":{"date-parts":[[2007,7,1]],"date-time":"2007-07-01T00:00:00Z","timestamp":1183248000000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2007,7]]},"abstract":"<jats:p>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 tree network, assuming an upper bound on the time of any edge traversal by an agent. The minimum number of agents capable of identifying a black hole is two. For a given tree and given starting node we are interested in the fastest-possible black hole search by two agents. For arbitrary trees we give a 5\/3-approximation algorithm for this problem. We give optimal black hole search algorithms for two \u2018extreme\u2019 classes of trees: the class of lines and the class of trees in which any internal node (including the root which is the starting node) has at least two children.<\/jats:p>","DOI":"10.1017\/s0963548306008133","type":"journal-article","created":{"date-parts":[[2006,11,3]],"date-time":"2006-11-03T12:35:18Z","timestamp":1162557318000},"page":"595-619","source":"Crossref","is-referenced-by-count":39,"title":["Searching for a Black Hole in Synchronous Tree Networks"],"prefix":"10.1017","volume":"16","author":[{"given":"JUREK","family":"CZYZOWICZ","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"DARIUSZ","family":"KOWALSKI","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"EURIPIDES","family":"MARKOU","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"ANDRZEJ","family":"PELC","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"56","published-online":{"date-parts":[[2007,7,1]]},"reference":[{"key":"S0963548306008133_manual_ref-9","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-68671-1_4"},{"key":"S0963548306008133_manual_ref-2","volume-title":"Proc. 15th International Symposium on Distributed Computing","author":"Dobrev","year":"2001"},{"key":"S0963548306008133_manual_ref-4","first-page":"34","volume-title":"Proc. 7th Int. Conference on Principles of Distributed Systems","author":"Dobrev","year":"2003"},{"key":"S0963548306008133_manual_ref-11","unstructured":"[11] Vitek, J. and Castagna, G. (1999) Mobile computations and hostile hosts. In Proc. Journ\u00e9es Francophones des Langages Applicatifs (JFLA 1999)."},{"key":"S0963548306008133_manual_ref-10","first-page":"155","volume-title":"Proc. 6th Int. Conf. on Intelligence and Services in Networks","author":"Schelderup","year":"1999"},{"key":"S0963548306008133_manual_ref-3","doi-asserted-by":"publisher","DOI":"10.1145\/571825.571853"},{"key":"S0963548306008133_manual_ref-5","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-68671-1_6"},{"key":"S0963548306008133_manual_ref-6","doi-asserted-by":"publisher","DOI":"10.1109\/ICDCS.2000.840953"},{"key":"S0963548306008133_manual_ref-7","unstructured":"[7] Klasing, R. , Markou, E. , Radzik, T. and Sarracco, F. Hardness and approximation results for black hole search in arbitrary networks. Theoret. Comput. Sci., to appear."},{"key":"S0963548306008133_manual_ref-1","unstructured":"[1] Dobrev, S. , Flocchini, P. , Kralovic, R. , Prencipe, G. Ruzicka, P. and Santoro, N. (2002) Black hole search by mobile agents in hypercubes and related networks. In Proc. 6th Int. Conference on Principles of Distributed Systems (OPODIS 2002), pp. 171\u2013182."},{"key":"S0963548306008133_manual_ref-8","unstructured":"[8] Ng, S. and Cheung, K. (1999) Protecting mobile agents against malicious hosts by intention of spreading. In Proc. Int. Conf. on Parallel and Distributed Processing and Applications (PDPTA'99), Vol. II ( Arabnia, H. , ed.), pp. 725\u2013729."}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548306008133","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,21]],"date-time":"2025-06-21T05:09:42Z","timestamp":1750482582000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548306008133\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,7]]},"references-count":11,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2007,1]]}},"alternative-id":["S0963548306008133"],"URL":"https:\/\/doi.org\/10.1017\/s0963548306008133","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,7]]}}}