{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,2]],"date-time":"2026-02-02T23:19:08Z","timestamp":1770074348398,"version":"3.49.0"},"publisher-location":"Berlin, Heidelberg","reference-count":28,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642240997","type":"print"},{"value":"9783642241000","type":"electronic"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011]]},"DOI":"10.1007\/978-3-642-24100-0_41","type":"book-chapter","created":{"date-parts":[[2011,10,19]],"date-time":"2011-10-19T06:20:40Z","timestamp":1319005240000},"page":"432-446","source":"Crossref","is-referenced-by-count":18,"title":["Black Hole Search with Finite Automata Scattered in a Synchronous Torus"],"prefix":"10.1007","author":[{"given":"J\u00e9r\u00e9mie","family":"Chalopin","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shantanu","family":"Das","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Arnaud","family":"Labourel","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Euripides","family":"Markou","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"41_CR1","doi-asserted-by":"crossref","unstructured":"Bender, M.A., Slonim, D.: The power of team exploration: Two robots can learn unlabeled directed graphs. In: Proceedings of 35th Annual Symposium on Foundations of Computer Science, pp. 75\u201385 (1994)","DOI":"10.1109\/SFCS.1994.365703"},{"key":"41_CR2","doi-asserted-by":"crossref","unstructured":"Chalopin, J., Das, S., Labourel, A., Markou, E.: Black hole search with finite automata scattered in a synchronous torus. arxiv:1106.6037 (2011)","DOI":"10.1007\/978-3-642-24100-0_41"},{"key":"41_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"186","DOI":"10.1007\/978-3-642-22212-2_17","volume-title":"Structural Information and Communication Complexity","author":"J. Chalopin","year":"2011","unstructured":"Chalopin, J., Das, S., Labourel, A., Markou, E.: Tight bounds for scattered black hole search in a ring. In: Kosowski, A., Yamashita, M. (eds.) SIROCCO 2011. LNCS, vol.\u00a06796, pp. 186\u2013197. Springer, Heidelberg (2011)"},{"key":"41_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"108","DOI":"10.1007\/978-3-540-75142-7_11","volume-title":"Distributed Computing","author":"J. Chalopin","year":"2007","unstructured":"Chalopin, J., Das, S., Santoro, N.: Rendezvous of mobile agents in unknown graphs with faulty links. In: Pelc, A. (ed.) DISC 2007. LNCS, vol.\u00a04731, pp. 108\u2013122. Springer, Heidelberg (2007)"},{"key":"41_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"320","DOI":"10.1007\/11945529_23","volume-title":"Principles of Distributed Systems","author":"C. Cooper","year":"2006","unstructured":"Cooper, C., Klasing, R., Radzik, T.: Searching for black-hole faults in a network using multiple agents. In: Shvartsman, M.M.A.A. (ed.) OPODIS 2006. LNCS, vol.\u00a04305, pp. 320\u2013332. Springer, Heidelberg (2006)"},{"key":"41_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"182","DOI":"10.1007\/978-3-642-11476-2_15","volume-title":"Structural Information and Communication Complexity","author":"J. Czyzowicz","year":"2010","unstructured":"Czyzowicz, J., Dobrev, S., Kr\u00e1lovi\u010d, R., Mikl\u00edk, S., Pardubsk\u00e1, D.: Black hole search in directed graphs. In: Kutten, S., \u017derovnik, J. (eds.) SIROCCO 2009. LNCS, vol.\u00a05869, pp. 182\u2013194. Springer, Heidelberg (2010)"},{"issue":"4","key":"41_CR7","doi-asserted-by":"publisher","first-page":"595","DOI":"10.1017\/S0963548306008133","volume":"16","author":"J. Czyzowicz","year":"2007","unstructured":"Czyzowicz, J., Kowalski, D., Markou, E., Pelc, A.: Searching for a black hole in synchronous tree networks. Combinatorics, Probability & Computing\u00a016(4), 595\u2013619 (2007)","journal-title":"Combinatorics, Probability & Computing"},{"issue":"3","key":"41_CR8","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1002\/(SICI)1097-0118(199911)32:3<265::AID-JGT6>3.0.CO;2-8","volume":"32","author":"X. Deng","year":"1999","unstructured":"Deng, X., Papadimitriou, C.H.: Exploring an unknown graph. Journal of Graph Theory\u00a032(3), 265\u2013297 (1999)","journal-title":"Journal of Graph Theory"},{"issue":"2","key":"41_CR9","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1002\/net.20095","volume":"47","author":"S. Dobrev","year":"2006","unstructured":"Dobrev, S., Flocchini, P., Kralovic, R., Prencipe, G., Ruzicka, P., Santoro, N.: Optimal search for a black hole in common interconnection networks. Networks\u00a047(2), 61\u201371 (2006)","journal-title":"Networks"},{"key":"41_CR10","unstructured":"Dobrev, S., Flocchini, P., Kralovic, R., Santoro, N.: Exploring a dangerous unknown graph using tokens. In: Proceedings of 5th IFIP International Conference on Theoretical Computer Science, pp. 131\u2013150 (2006)"},{"key":"41_CR11","doi-asserted-by":"crossref","unstructured":"Dobrev, S., Flocchini, P., Prencipe, G., Santoro, N.: Multiple agents rendezvous in a ring in spite of a black hole. In: Proceedings of 6th International Conference on Principles of Distributed Systems, pp. 34\u201346 (2003)","DOI":"10.1007\/978-3-540-27860-3_6"},{"issue":"1","key":"41_CR12","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00446-006-0154-y","volume":"19","author":"S. Dobrev","year":"2006","unstructured":"Dobrev, S., Flocchini, P., Prencipe, G., Santoro, N.: Searching for a black hole in arbitrary networks: Optimal mobile agents protocols. Distributed Computing\u00a019(1), 1\u201319 (2006)","journal-title":"Distributed Computing"},{"key":"41_CR13","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1007\/s00453-006-1232-z","volume":"48","author":"S. Dobrev","year":"2007","unstructured":"Dobrev, S., Flocchini, P., Prencipe, G., Santoro, N.: Mobile search for a black hole in an anonymous ring. Algorithmica\u00a048, 67\u201390 (2007)","journal-title":"Algorithmica"},{"key":"41_CR14","doi-asserted-by":"crossref","unstructured":"Dobrev, S., Flocchini, P., Santoro, N.: Improved bounds for optimal black hole search in a network with a map. In: Proceedings of 10th International Colloquium on Structural Information and Communication Complexity, pp. 111\u2013122 (2004)","DOI":"10.1007\/978-3-540-27796-5_11"},{"key":"41_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1007\/11758471_16","volume-title":"Algorithms and Complexity","author":"S. Dobrev","year":"2006","unstructured":"Dobrev, S., Kr\u00e1lovi\u010d, R., Santoro, N., Shi, W.: Black hole search in asynchronous rings using tokens. In: Calamoneri, T., Finocchi, I., Italiano, G.F. (eds.) CIAC 2006. LNCS, vol.\u00a03998, pp. 139\u2013150. Springer, Heidelberg (2006)"},{"key":"41_CR16","doi-asserted-by":"crossref","unstructured":"Dobrev, S., Santoro, N., Shi, W.: Scattered black hole search in an oriented ring using tokens. In: Proceedings of IEEE International Parallel and Distributed Processing Symposium, pp. 1\u20138 (2007)","DOI":"10.1109\/IPDPS.2007.370460"},{"issue":"6","key":"41_CR17","doi-asserted-by":"publisher","first-page":"1355","DOI":"10.1142\/S0129054108006327","volume":"19","author":"S. Dobrev","year":"2008","unstructured":"Dobrev, S., Santoro, N., Shi, W.: Using scattered mobile agents to locate a black hole in an un-oriented ring with tokens. International Journal of Foundations of Computer Science\u00a019(6), 1355\u20131372 (2008)","journal-title":"International Journal of Foundations of Computer Science"},{"key":"41_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"227","DOI":"10.1007\/978-3-540-87779-0_16","volume-title":"Distributed Computing","author":"P. Flocchini","year":"2008","unstructured":"Flocchini, P., Ilcinkas, D., Santoro, N.: Ping pong in dangerous graphs: Optimal black hole search with pure tokens. In: Taubenfeld, G. (ed.) DISC 2008. LNCS, vol.\u00a05218, pp. 227\u2013241. Springer, Heidelberg (2008)"},{"key":"41_CR19","doi-asserted-by":"crossref","unstructured":"Flocchini, P., Kellett, M., Mason, P., Santoro, N.: Map construction and exploration by mobile agents scattered in a dangerous network. In: Proceedings of IEEE International Symposium on Parallel & Distributed Processing, pp. 1\u201310 (2009)","DOI":"10.1109\/IPDPS.2009.5161080"},{"key":"41_CR20","doi-asserted-by":"publisher","first-page":"166","DOI":"10.1002\/net.20127","volume":"48","author":"P. Fraigniaud","year":"2006","unstructured":"Fraigniaud, P., Gasieniec, L., Kowalski, D., Pelc, A.: Collective tree exploration. Networks\u00a048, 166\u2013177 (2006)","journal-title":"Networks"},{"key":"41_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"128","DOI":"10.1007\/978-3-642-05434-1_13","volume-title":"Algorithmic Aspects of Wireless Sensor Networks","author":"P. Glaus","year":"2009","unstructured":"Glaus, P.: Locating a black hole without the knowledge of incoming link. In: Dolev, S. (ed.) ALGOSENSORS 2009. LNCS, vol.\u00a05804, pp. 128\u2013138. Springer, Heidelberg (2009)"},{"issue":"2-3","key":"41_CR22","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1016\/j.tcs.2007.04.024","volume":"384","author":"R. Klasing","year":"2007","unstructured":"Klasing, R., Markou, E., Radzik, T., Sarracco, F.: Hardness and approximation results for black hole search in arbitrary graphs. Theoretical Computer Science\u00a0384(2-3), 201\u2013221 (2007)","journal-title":"Theoretical Computer Science"},{"issue":"4","key":"41_CR23","doi-asserted-by":"publisher","first-page":"216","DOI":"10.1002\/net.20233","volume":"52","author":"R. Klasing","year":"2008","unstructured":"Klasing, R., Markou, E., Radzik, T., Sarracco, F.: Approximation bounds for black hole search problems. Networks\u00a052(4), 216\u2013226 (2008)","journal-title":"Networks"},{"key":"41_CR24","doi-asserted-by":"crossref","unstructured":"Kosowski, A., Navarra, A., Pinotti, C.: Synchronization helps robots to detect black holes in directed graphs. In: Proceedings of 13th International Conference on Principles of Distributed Systems, pp. 86\u201398 (2009)","DOI":"10.1007\/978-3-642-10877-8_9"},{"key":"41_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1007\/978-3-642-13284-1_13","volume-title":"Structural Information and Communication Complexity","author":"R. Kr\u00e0lovi\u010d","year":"2010","unstructured":"Kr\u00e0lovi\u010d, R., Mikl\u00edk, S.: Periodic data retrieval problem in rings containing a malicious host. In: Patt-Shamir, B., Ekim, T. (eds.) SIROCCO 2010. LNCS, vol.\u00a06058, pp. 157\u2013167. Springer, Heidelberg (2010)"},{"issue":"9","key":"41_CR26","doi-asserted-by":"publisher","first-page":"896","DOI":"10.1016\/j.dam.2011.01.020","volume":"159","author":"E. Kranakis","year":"2011","unstructured":"Kranakis, E., Krizanc, D., Markou, E.: Deterministic symmetric rendezvous with tokens in a synchronous torus. Discrete Applied Mathematics\u00a0159(9), 896\u2013923 (2011)","journal-title":"Discrete Applied Mathematics"},{"key":"41_CR27","unstructured":"Shannon, C.E.: Presentation of a maze-solving machine. In: Proceedings of 8th Conference of the Josiah Macy Jr. Found (Cybernetics), pp. 173\u2013180 (1951)"},{"key":"41_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"670","DOI":"10.1007\/978-3-642-05118-0_46","volume-title":"Stabilization, Safety, and Security of Distributed Systems","author":"W. Shi","year":"2009","unstructured":"Shi, W.: Black hole search with tokens in interconnected networks. In: Guerraoui, R., Petit, F. (eds.) SSS 2009. LNCS, vol.\u00a05873, pp. 670\u2013682. Springer, Heidelberg (2009)"}],"container-title":["Lecture Notes in Computer Science","Distributed Computing"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-24100-0_41","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,18]],"date-time":"2019-06-18T02:47:53Z","timestamp":1560826073000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-24100-0_41"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642240997","9783642241000"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-24100-0_41","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011]]}}}