{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,2]],"date-time":"2026-02-02T21:49:08Z","timestamp":1770068948133,"version":"3.49.0"},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642354755","type":"print"},{"value":"9783642354762","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-35476-2_17","type":"book-chapter","created":{"date-parts":[[2012,12,13]],"date-time":"2012-12-13T20:48:14Z","timestamp":1355431694000},"page":"239-253","source":"Crossref","is-referenced-by-count":11,"title":["Black Hole Search and Exploration in Unoriented Tori with Synchronous Scattered Finite Automata"],"prefix":"10.1007","author":[{"given":"Euripides","family":"Markou","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michel","family":"Paquette","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"17_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1007\/978-3-642-31104-8_24","volume-title":"Structural Information and Communication Complexity","author":"B. Balamohan","year":"2012","unstructured":"Balamohan, B., Dobrev, S., Flocchini, P., Santoro, N.: Asynchronous Exploration of an Unknown Anonymous Dangerous Graph with O(1) Pebbles. In: Even, G., Halld\u00f3rsson, M.M. (eds.) SIROCCO 2012. LNCS, vol.\u00a07355, pp. 279\u2013290. Springer, Heidelberg (2012)"},{"key":"17_CR2","doi-asserted-by":"crossref","unstructured":"Bender, M.A., Slonim, D.: The power of team exploration: Two robots can learn unlabeled directed graphs. In: Proc. of 35th Annual Symp. on Foundations of Computer Science, pp. 75\u201385 (1994)","DOI":"10.1109\/SFCS.1994.365703"},{"key":"17_CR3","doi-asserted-by":"crossref","unstructured":"Blum, M., Kozen, D.: On the power of the compass (or, why mazes are easier to search than graphs). In: Proc. of 19th Symp. on Foundations of Computer Science, pp. 132\u2013142 (1978)","DOI":"10.1109\/SFCS.1978.30"},{"issue":"1","key":"17_CR4","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1002\/mana.19780860120","volume":"86","author":"L. Budach","year":"1978","unstructured":"Budach, L.: Automata and labyrinths. Mathematische Nachrichten\u00a086(1), 195\u2013282 (1978)","journal-title":"Mathematische Nachrichten"},{"key":"17_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"432","DOI":"10.1007\/978-3-642-24100-0_41","volume-title":"Distributed Computing","author":"J. Chalopin","year":"2011","unstructured":"Chalopin, J., Das, S., Labourel, A., Markou, E.: Black Hole Search with Finite Automata Scattered in a Synchronous Torus. In: Peleg, D. (ed.) DISC 2011. LNCS, vol.\u00a06950, pp. 432\u2013446. Springer, Heidelberg (2011)"},{"key":"17_CR6","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":"17_CR7","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)"},{"issue":"2,3","key":"17_CR8","doi-asserted-by":"crossref","first-page":"229","DOI":"10.3233\/FUN-2006-712-305","volume":"71","author":"J. Czyzowicz","year":"2006","unstructured":"Czyzowicz, J., Kowalski, D., Markou, E., Pelc, A.: Complexity of searching for a black hole. Fundamenta Informaticae\u00a071(2,3), 229\u2013242 (2006)","journal-title":"Fundamenta Informaticae"},{"issue":"3","key":"17_CR9","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. J. of Graph Theory\u00a032(3), 265\u2013297 (1999)","journal-title":"J. of Graph Theory"},{"key":"17_CR10","series-title":"IFIP","first-page":"131","volume-title":"TCS 2006","author":"S. Dobrev","year":"2006","unstructured":"Dobrev, S., Flocchini, P., Kr\u00e1lovic, R., Santoro, N.: Exploring an Unknown Graph to Locate a Black Hole Using Tokens. In: Navarro, G., Bertossi, L., Kohayakawa, Y. (eds.) TCS 2006. IFIP, vol.\u00a0209, pp. 131\u2013150. Springer, Boston (2006)"},{"issue":"1","key":"17_CR11","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":"17_CR12","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"},{"issue":"6","key":"17_CR13","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-oriened ring with tokens. Int. J. of Foundations of Computer Science\u00a019(6), 1355\u20131372 (2008)","journal-title":"Int. J. of Foundations of Computer Science"},{"issue":"3-4","key":"17_CR14","doi-asserted-by":"publisher","first-page":"1006","DOI":"10.1007\/s00453-011-9496-3","volume":"62","author":"P. Flocchini","year":"2012","unstructured":"Flocchini, P., Ilcinkas, D., Santoro, N.: Ping pong in dangerous graphs: Optimal black hole search with pebbles. Algorithmica\u00a062(3-4), 1006\u20131033 (2012)","journal-title":"Algorithmica"},{"key":"17_CR15","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: Proc. of IEEE Int. Symp. on Parallel & Distributed Processing, pp. 1\u201310 (2009)","DOI":"10.1109\/IPDPS.2009.5161080"},{"key":"17_CR16","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"},{"issue":"2-3","key":"17_CR17","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"},{"key":"17_CR18","series-title":"LNCS","first-page":"86","volume-title":"OPODIS","author":"A. Kosowski","year":"2009","unstructured":"Kosowski, A., Navarra, A., Pinotti, C.M.: Synchronization Helps Robots to Detect Black Holes in Directed Graphs. In: Abdelzaher, T., Raynal, M., Santoro, N. (eds.) OPODIS. LNCS, vol.\u00a05923, pp. 86\u201398. Springer, Heidelberg (2009)"},{"key":"17_CR19","unstructured":"Kozen, D.: Automata and planar graphs. In: Proc. of Fundamentals of Computation Theory, pp. 243\u2013254 (1979)"},{"issue":"1","key":"17_CR20","doi-asserted-by":"publisher","first-page":"80","DOI":"10.1006\/jpdc.1997.1389","volume":"46","author":"B. Mans","year":"1997","unstructured":"Mans, B.: Optimal distributed algorithms in unlabeled tori and chordal rings. Journal of Parallel and Distributed Computing\u00a046(1), 80\u201390 (1997)","journal-title":"Journal of Parallel and Distributed Computing"},{"key":"17_CR21","unstructured":"Rabin, M.: Maze threading automata. Seminar talk presented at the University of California at Berkeley (October 1967)"},{"key":"17_CR22","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1007\/BF00288647","volume":"13","author":"H. Rollik","year":"1980","unstructured":"Rollik, H.: Automaten in planaren graphen. Acta Informatica\u00a013, 287\u2013298 (1980)","journal-title":"Acta Informatica"},{"key":"17_CR23","unstructured":"Shannon, C.E.: Presentation of a maze-solving machine. In: Proc. of 8th Conf. of the Josiah Macy Jr. Found (Cybernetics), pp. 173\u2013180 (1951)"},{"key":"17_CR24","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","Principles of Distributed Systems"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-35476-2_17.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,23]],"date-time":"2025-04-23T17:39:51Z","timestamp":1745429991000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-35476-2_17"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642354755","9783642354762"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-35476-2_17","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012]]}}}