{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,5]],"date-time":"2026-10-05T09:17:10Z","timestamp":1791191830990,"version":"4.1.0"},"reference-count":42,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2012,1,7]],"date-time":"2012-01-07T00:00:00Z","timestamp":1325894400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2013,3]]},"DOI":"10.1007\/s00453-011-9611-5","type":"journal-article","created":{"date-parts":[[2012,1,6]],"date-time":"2012-01-06T17:56:27Z","timestamp":1325872587000},"page":"562-583","source":"Crossref","is-referenced-by-count":64,"title":["Computing Without Communicating: Ring Exploration by Asynchronous Oblivious Robots"],"prefix":"10.1007","volume":"65","author":[{"given":"Paola","family":"Flocchini","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"David","family":"Ilcinkas","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Andrzej","family":"Pelc","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Nicola","family":"Santoro","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2012,1,7]]},"reference":[{"key":"9611_CR1","doi-asserted-by":"crossref","first-page":"56","DOI":"10.1137\/050645221","volume":"36","author":"N. Agmon","year":"2006","unstructured":"Agmon, N., Peleg, D.: Fault-tolerant gathering algorithms for autonomous mobile robots. SIAM J. Comput. 36, 56\u201382 (2006)","journal-title":"SIAM J. Comput."},{"key":"9611_CR2","doi-asserted-by":"crossref","first-page":"1164","DOI":"10.1137\/S009753979732428X","volume":"29","author":"S. Albers","year":"2000","unstructured":"Albers, S., Henzinger, M.R.: Exploring unknown environments. SIAM J. Comput. 29, 1164\u20131188 (2000)","journal-title":"SIAM J. Comput."},{"key":"9611_CR3","doi-asserted-by":"crossref","DOI":"10.1145\/1921659.1921663","volume":"7","author":"C. Amb\u00fchl","year":"2011","unstructured":"Amb\u00fchl, C., Gasieniec, L., Pelc, A., Radzik, T., Zhang, X.: Tree exploration with logarithmic memory. ACM Trans. Algorithms 7, article\u00a017 (2011)","journal-title":"ACM Trans. Algorithms"},{"key":"9611_CR4","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1016\/0166-218X(95)00054-U","volume":"68","author":"I. Averbakh","year":"1996","unstructured":"Averbakh, I., Berman, O.: A heuristic with worst-case analysis for minimax routing of two traveling salesmen on a tree. Discrete Appl. Math. 68, 17\u201332 (1996)","journal-title":"Discrete Appl. Math."},{"key":"9611_CR5","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1016\/S0166-218X(97)89161-5","volume":"75","author":"I. Averbakh","year":"1997","unstructured":"Averbakh, I., Berman, O.: (p\u22121)\/(p+1)-approximate algorithms for p-traveling salesmen problems on a tree with minmax objective. Discrete Appl. Math. 75, 201\u2013216 (1997)","journal-title":"Discrete Appl. Math."},{"key":"9611_CR6","doi-asserted-by":"crossref","first-page":"321","DOI":"10.1145\/225298.225337","volume-title":"Proceedings of the 8th Annual Conference on Computational Learning Theory (COLT 1995)","author":"B. Awerbuch","year":"1995","unstructured":"Awerbuch, B., Betke, M., Rivest, R., Singh, M.: Piecemeal graph learning by a mobile robot. In: Proceedings of the 8th Annual Conference on Computational Learning Theory (COLT 1995), pp. 321\u2013328 (1995)"},{"key":"9611_CR7","first-page":"269","volume-title":"Proceedings of the 30th Annual ACM Symposium on the Theory of Computing (STOC 1998)","author":"M.A. Bender","year":"1998","unstructured":"Bender, M.A., Fernandez, A., Ron, D., Sahai, A., Vadhan, S.: The power of a pebble: exploring and mapping directed graphs. In: Proceedings of the 30th Annual ACM Symposium on the Theory of Computing (STOC 1998), pp. 269\u2013278 (1998)"},{"key":"9611_CR8","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1109\/SFCS.1994.365703","volume-title":"Proceedings of the 35th Annual Symposium on Foundations of Computer Science (FOCS 1994)","author":"M.A. Bender","year":"1994","unstructured":"Bender, M.A., Slonim, D.: The power of team exploration: Two robots can learn unlabeled directed graphs. In: Proceedings of the 35th Annual Symposium on Foundations of Computer Science (FOCS 1994), pp. 75\u201385 (1994)"},{"key":"9611_CR9","first-page":"231","volume":"18","author":"M. Betke","year":"1995","unstructured":"Betke, M., Rivest, R., Singh, M.: Piecemeal learning of an unknown environment. Mach. Learn. 18, 231\u2013254 (1995)","journal-title":"Mach. Learn."},{"key":"9611_CR10","series-title":"LNCS","first-page":"208","volume-title":"Proceedings of the 36th Int. Workshop on Graph Theoretic Concepts in Computer Science (WG 2010)","author":"J. Chalopin","year":"2010","unstructured":"Chalopin, J., Flocchini, P., Mans, B., Santoro, N.: Network exploration by silent and oblivious robots. In: Proceedings of the 36th Int. Workshop on Graph Theoretic Concepts in Computer Science (WG 2010). LNCS, vol. 6410, pp. 208\u2013219. Springer, Berlin (2010)"},{"key":"9611_CR11","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"1181","DOI":"10.1007\/3-540-45061-0_90","volume-title":"Proceedings of the 30th International Colloquium on Automata, Languages and Programming (ICALP 2003)","author":"M. Cieliebak","year":"2003","unstructured":"Cieliebak, M., Flocchini, P., Prencipe, G., Santoro, N.: Solving the robots gathering problem. In: Proceedings of the 30th International Colloquium on Automata, Languages and Programming (ICALP 2003). LNCS, vol. 2719, pp. 1181\u20131196. Springer, Berlin (2003)"},{"key":"9611_CR12","doi-asserted-by":"crossref","first-page":"1516","DOI":"10.1137\/S0097539704446475","volume":"34","author":"R. Cohen","year":"2005","unstructured":"Cohen, R., Peleg, D.: Convergence properties of the gravitational algorithm in asynchronous robot systems. SIAM J. Comput. 34, 1516\u20131528 (2005)","journal-title":"SIAM J. Comput."},{"key":"9611_CR13","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1007\/978-3-540-27796-5_8","volume-title":"Proceedings of the 11th International Colloquium on Structural Information and Communication Complexity (SIROCCO 2004)","author":"R. Cohen","year":"2004","unstructured":"Cohen, R., Peleg, D.: Robot convergence via center-of-gravity algorithms. In: Proceedings of the 11th International Colloquium on Structural Information and Communication Complexity (SIROCCO 2004). LNCS, vol. 3104, pp. 79\u201388. Springer, Berlin (2004)"},{"key":"9611_CR14","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"320","DOI":"10.1007\/11945529_23","volume-title":"Proceedings of the 10th International Conference on Principles of Distributed Systems (OPODIS 2006)","author":"C. Cooper","year":"2006","unstructured":"Cooper, C., Klasing, R., Radzik, T.: Searching for black-hole faults in a network using multiple agents. In: Proceedings of the 10th International Conference on Principles of Distributed Systems (OPODIS 2006). LNCS, vol. 4288, pp. 320\u2013332. Springer, Berlin (2006)"},{"key":"9611_CR15","doi-asserted-by":"crossref","first-page":"481","DOI":"10.1016\/j.tcs.2008.10.005","volume":"410","author":"J. Czyzowicz","year":"2009","unstructured":"Czyzowicz, J., Gasieniec, L., Pelc, A.: Gathering few fat mobile robots in the plane. Theor. Comput. Sci. 410, 481\u2013499 (2009)","journal-title":"Theor. Comput. Sci."},{"key":"9611_CR16","doi-asserted-by":"crossref","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. Comb. Probab. Comput. 16, 595\u2013619 (2007)","journal-title":"Comb. Probab. Comput."},{"key":"9611_CR17","doi-asserted-by":"crossref","first-page":"34","DOI":"10.1016\/j.tcs.2007.05.011","volume":"385","author":"S. Das","year":"2007","unstructured":"Das, S., Flocchini, P., Kutten, S., Nayak, A., Santoro, N.: Map construction of unknown graphs by multiple agents. Theor. Comput. Sci. 385, 34\u201348 (2007)","journal-title":"Theor. Comput. Sci."},{"key":"9611_CR18","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1016\/j.tcs.2008.01.050","volume":"396","author":"X. D\u00e9fago","year":"2008","unstructured":"D\u00e9fago, X., Souissi, S.: Non-uniform circle formation algorithm for oblivious mobile robots with convergence toward uniformity. Theor. Comput. Sci. 396, 97\u2013112 (2008)","journal-title":"Theor. Comput. Sci."},{"key":"9611_CR19","doi-asserted-by":"crossref","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. Graph Theory 32, 265\u2013297 (1999)","journal-title":"J. Graph Theory"},{"key":"9611_CR20","doi-asserted-by":"crossref","first-page":"343","DOI":"10.1016\/j.tcs.2004.07.031","volume":"326","author":"A. Dessmark","year":"2004","unstructured":"Dessmark, A., Pelc, A.: Optimal graph exploration without good maps. Theor. Comput. Sci. 326, 343\u2013362 (2004)","journal-title":"Theor. Comput. Sci."},{"key":"9611_CR21","first-page":"9:1","volume-title":"Proceedings of the 3rd International ACM SIGOPS\/SIGACT Workshop on Reliability, Availability, and Security (WRAS 2010)","author":"S. Devismes","year":"2010","unstructured":"Devismes, S.: Optimal exploration of small rings. In: Proceedings of the 3rd International ACM SIGOPS\/SIGACT Workshop on Reliability, Availability, and Security (WRAS 2010), pp. 9:1\u20139:6 (2010)"},{"key":"9611_CR22","series-title":"LNCS","first-page":"195","volume-title":"Proceedings of the 16th International Colloquium on Structural Information and Communication Complexity (SIROCCO 2009)","author":"S. Devismes","year":"2009","unstructured":"Devismes, S., Petit, F., Tixeuil, S.: Optimal probabilistic ring exploration by semi-synchronous oblivious robots. In: Proceedings of the 16th International Colloquium on Structural Information and Communication Complexity (SIROCCO 2009). LNCS, vol. 5869, pp. 195\u2013208. Springer, Berlin (2009)"},{"key":"9611_CR23","doi-asserted-by":"crossref","first-page":"38","DOI":"10.1016\/j.jalgor.2003.10.002","volume":"51","author":"K. Diks","year":"2004","unstructured":"Diks, K., Fraigniaud, P., Kranakis, E., Pelc, A.: Tree exploration with little memory. J. Algorithms 51, 38\u201363 (2004)","journal-title":"J. Algorithms"},{"key":"9611_CR24","first-page":"807","volume-title":"Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2001)","author":"C.A. Duncan","year":"2001","unstructured":"Duncan, C.A., Kobourov, S.G., Kumar, V.S.A.: Optimal constrained graph exploration. In: Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2001), pp. 807\u2013814 (2001)"},{"key":"9611_CR25","series-title":"LNCS","first-page":"11","volume-title":"Proceedings of the 13th European Symposium on Algorithms (ESA 2005)","author":"R. Fleischer","year":"2005","unstructured":"Fleischer, R., Trippen, G.: Exploring an unknown graph efficiently. In: Proceedings of the 13th European Symposium on Algorithms (ESA 2005). LNCS, vol. 3669, pp. 11\u201322. Springer, Berlin (2005)"},{"key":"9611_CR26","doi-asserted-by":"crossref","first-page":"1544","DOI":"10.1016\/j.tcs.2010.01.004","volume":"411","author":"P. Flocchini","year":"2010","unstructured":"Flocchini, P., Ilcinkas, D., Pelc, A., Santoro, N.: Remembering without memory: tree exploration by asynchronous oblivious robots. Theor. Comput. Sci. 411, 1544\u20131557 (2010)","journal-title":"Theor. Comput. Sci."},{"key":"9611_CR27","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1007\/978-3-540-77096-1_8","volume-title":"Proceedings of the 11th International Conference on Principles of Distributed Systems (OPODIS 2007)","author":"P. Flocchini","year":"2007","unstructured":"Flocchini, P., Ilcinkas, D., Pelc, A., Santoro, N.: Computing without communicating: ring exploration by asynchronous oblivious robots. In: Proceedings of the 11th International Conference on Principles of Distributed Systems (OPODIS 2007). LNCS, vol. 4878, pp. 105\u2013118. Springer, Berlin (2007)"},{"key":"9611_CR28","doi-asserted-by":"crossref","unstructured":"Flocchini, P., Ilcinkas, D., Santoro, N.: Ping-Pong in dangerous graphs: Optimal black hole search with pure tokens. Algorithmica (2011, in press)","DOI":"10.1007\/s00453-011-9496-3"},{"key":"9611_CR29","doi-asserted-by":"crossref","unstructured":"Flocchini, P., Prencipe, G., Santoro, N.: Computing by mobile robotic sensors. Chap.\u00a03 of [37] (2011)","DOI":"10.2200\/S00440ED1V01Y201208DCT010"},{"key":"9611_CR30","doi-asserted-by":"crossref","first-page":"412","DOI":"10.1016\/j.tcs.2008.07.026","volume":"407","author":"P. Flocchini","year":"2008","unstructured":"Flocchini, P., Prencipe, G., Santoro, N., Widmayer, P.: Arbitrary pattern formation by asynchronous, anonymous, oblivious robots. Theor. Comput. Sci. 407, 412\u2013447 (2008)","journal-title":"Theor. Comput. Sci."},{"key":"9611_CR31","doi-asserted-by":"crossref","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 48, 166\u2013177 (2006)","journal-title":"Networks"},{"key":"9611_CR32","doi-asserted-by":"crossref","first-page":"178","DOI":"10.1137\/0207017","volume":"7","author":"G.N. Frederickson","year":"1978","unstructured":"Frederickson, G.N., Hecht, M.S., Kim, C.E.: Approximation algorithms for some routing problems. SIAM J. Comput. 7, 178\u2013193 (1978)","journal-title":"SIAM J. Comput."},{"key":"9611_CR33","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"150","DOI":"10.1007\/978-3-642-22212-2_14","volume-title":"Proceedings of the 18th International Colloquium on Structural Information and Communication Complexity (SIROCCO 2011)","author":"S. Kamei","year":"2011","unstructured":"Kamei, S., Lamani, A., Ooshita, F., Tixeuil, S.: Asynchronous mobile robot gathering from symmetric configurations without global multiplicity detection. In: Proceedings of the 18th International Colloquium on Structural Information and Communication Complexity (SIROCCO 2011). LNCS, vol. 6796, pp. 150\u2013161. Springer, Berlin (2011)"},{"key":"9611_CR34","doi-asserted-by":"crossref","first-page":"3235","DOI":"10.1016\/j.tcs.2010.05.020","volume":"411","author":"R. Klasing","year":"2010","unstructured":"Klasing, R., Kosowski, A., Navarra, A.: Taking advantage of symmetries: Gathering of many asynchronous oblivious robots on a ring. Theor. Comput. Sci. 411, 3235\u20133246 (2010)","journal-title":"Theor. Comput. Sci."},{"key":"9611_CR35","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1016\/j.tcs.2007.09.032","volume":"390","author":"R. Klasing","year":"2008","unstructured":"Klasing, R., Markou, E., Pelc, A.: Gathering asynchronous oblivious mobile robots in a ring. Theor. Comput. Sci. 390, 27\u201339 (2008)","journal-title":"Theor. Comput. Sci."},{"key":"9611_CR36","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"183","DOI":"10.1007\/978-3-642-13284-1_15","volume-title":"Proceedings of the 17th International Colloquium on Structural Information and Communication Complexity (SIROCCO 2010)","author":"A. Lamani","year":"2010","unstructured":"Lamani, A., Gradinariu Potop-Butucaru, M., Tixeuil, S.: Optimal deterministic ring exploration with oblivious asynchronous robots. In: Proceedings of the 17th International Colloquium on Structural Information and Communication Complexity (SIROCCO 2010). LNCS, vol. 6058, pp. 183\u2013196. Springer, Berlin (2010)"},{"key":"9611_CR37","volume-title":"Theoretical Aspects of Distributed Computing in Sensor Networks","year":"2011","unstructured":"Nikoletseas, S., Rolim, J. (eds.): Theoretical Aspects of Distributed Computing in Sensor Networks. Springer, Berlin (2011)"},{"key":"9611_CR38","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1006\/jagm.1999.1043","volume":"33","author":"P. Panaite","year":"1999","unstructured":"Panaite, P., Pelc, A.: Exploring unknown undirected graphs. J. Algorithms 33, 281\u2013295 (1999)","journal-title":"J. Algorithms"},{"key":"9611_CR39","doi-asserted-by":"crossref","first-page":"222","DOI":"10.1016\/j.tcs.2007.04.023","volume":"384","author":"G. Prencipe","year":"2007","unstructured":"Prencipe, G.: Impossibility of gathering by a set of autonomous mobile robots. Theor. Comput. Sci. 384, 222\u2013231 (2007)","journal-title":"Theor. Comput. Sci."},{"key":"9611_CR40","doi-asserted-by":"crossref","first-page":"269","DOI":"10.2307\/3619207","volume":"81","author":"S.M. Ruiz","year":"1997","unstructured":"Ruiz, S.M.: A result on prime numbers. Math. Gaz. 81, 269 (1997)","journal-title":"Math. Gaz."},{"key":"9611_CR41","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"333","DOI":"10.1007\/11945529_24","volume-title":"Proceedings of the 10th International Conference on Principles of Distributed Systems (OPODIS 2006)","author":"S. Souissi","year":"2006","unstructured":"Souissi, S., D\u00e9fago, X., Yamashita, M.: Gathering asynchronous mobile robots with inaccurate compasses. In: Proceedings of the 10th International Conference on Principles of Distributed Systems (OPODIS 2006). LNCS, vol. 4305, pp. 333\u2013349. Springer, Berlin (2006)"},{"key":"9611_CR42","doi-asserted-by":"crossref","first-page":"1347","DOI":"10.1137\/S009753979628292X","volume":"28","author":"I. Suzuki","year":"1999","unstructured":"Suzuki, I., Yamashita, M.: Distributed anonymous mobile robots: formation of geometric patterns. SIAM J. Comput. 28, 1347\u20131363 (1999)","journal-title":"SIAM J. Comput."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-011-9611-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-011-9611-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-011-9611-5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,18]],"date-time":"2025-03-18T15:28:58Z","timestamp":1742311738000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-011-9611-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,1,7]]},"references-count":42,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2013,3]]}},"alternative-id":["9611"],"URL":"https:\/\/doi.org\/10.1007\/s00453-011-9611-5","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,1,7]]}}}