{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,3,12]],"date-time":"2024-03-12T14:47:22Z","timestamp":1710254842930},"reference-count":9,"publisher":"World Scientific Pub Co Pte Lt","issue":"06","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2008,12]]},"abstract":" A black hole in a network is a highly harmful host that disposes of any incoming agents upon their arrival. Determining the location of a black hole in a ring network has been studied when each node is equipped with a whiteboard. Recently, the Black Hole Search problem was solved in a less demanding and less expensive token model with co-located agents. Whether the problem can be solved with scattered agents in a token model remains an open problem. <\/jats:p> In this paper, we show not only that a black hole can be located in a ring using tokens with scattered agents, but also that the problem is solvable even if the ring is un-oriented. More precisely, first we prove that the black hole search problem can be solved using only three scattered agents. We then show that, with K (K \u2a7e 4) scattered agents, the black hole can be located in O(kn + n log n) moves. Moreover, when K (K \u2a7e K) is a constant number, the move cost can be reduced to O(n log n), which is optimal. These results hold even if both agents and nodes are anonymous. <\/jats:p>","DOI":"10.1142\/s0129054108006327","type":"journal-article","created":{"date-parts":[[2009,1,5]],"date-time":"2009-01-05T09:36:29Z","timestamp":1231148189000},"page":"1355-1372","source":"Crossref","is-referenced-by-count":24,"title":["USING SCATTERED MOBILE AGENTS TO LOCATE A BLACK HOLE IN AN UN-ORIENTED RING WITH TOKENS"],"prefix":"10.1142","volume":"19","author":[{"given":"STEFAN","family":"DOBREV","sequence":"first","affiliation":[{"name":"School of Information Technology and Engineering (SITE)University of Ottawa, 800 King Edward Ottawa, Ontario, K1N 6N5, Canada"}]},{"given":"NICOLA","family":"SANTORO","sequence":"additional","affiliation":[{"name":"School of Computer Science, Carleton University, 1125 Colonel By Drive, Ottawa, Ontario, K1S 5B6, Canada"}]},{"given":"WEI","family":"SHI","sequence":"additional","affiliation":[{"name":"School of Computer Science, Carleton University, 1125 Colonel By Drive, Ottawa, Ontario, K1S 5B6, Canada"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"reference":[{"key":"rf1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-005-1223-5"},{"key":"rf4","first-page":"229","volume":"71","author":"Czyzowicz J.","journal-title":"Fundamenta Informatica"},{"key":"rf5","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548306008133"},{"key":"rf6","doi-asserted-by":"publisher","DOI":"10.1002\/net.20095"},{"key":"rf8","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-006-1232-z"},{"key":"rf9","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-006-0154-y"},{"key":"rf15","doi-asserted-by":"publisher","DOI":"10.1109\/35.689634"},{"key":"rf16","doi-asserted-by":"publisher","DOI":"10.1007\/11429647_17"},{"key":"rf17","doi-asserted-by":"publisher","DOI":"10.1016\/S0140-3664(99)00083-3"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054108006327","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T00:32:47Z","timestamp":1565137967000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054108006327"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,12]]},"references-count":9,"journal-issue":{"issue":"06","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[2008,12]]}},"alternative-id":["10.1142\/S0129054108006327"],"URL":"https:\/\/doi.org\/10.1142\/s0129054108006327","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,12]]}}}