{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,21]],"date-time":"2026-09-21T09:43:10Z","timestamp":1789983790248,"version":"4.0.1"},"publisher-location":"Berlin, Heidelberg","reference-count":30,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540770954","type":"print"},{"value":"9783540770961","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-77096-1_8","type":"book-chapter","created":{"date-parts":[[2008,4,11]],"date-time":"2008-04-11T11:44:46Z","timestamp":1207914286000},"page":"105-118","source":"Crossref","is-referenced-by-count":30,"title":["Computing Without Communicating: Ring Exploration by Asynchronous Oblivious Robots"],"prefix":"10.1007","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","reference":[{"issue":"1","key":"8_CR1","doi-asserted-by":"publisher","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.\u00a036(1), 56\u201382 (2006)","journal-title":"SIAM J. Comput."},{"key":"8_CR2","doi-asserted-by":"publisher","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.\u00a029, 1164\u20131188 (2000)","journal-title":"SIAM J. Comput."},{"key":"8_CR3","doi-asserted-by":"publisher","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. Discr. Appl. Math.\u00a068, 17\u201332 (1996)","journal-title":"Discr. Appl. Math."},{"key":"8_CR4","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1016\/S0166-218X(97)89161-5","volume":"75","author":"I. Averbakh","year":"1997","unstructured":"Averbakh, I., Berman, O.: (p\u2009\u2212\u20091)\/(p\u2009+\u20091)-approximate algorithms for p-traveling salesmen problems on a tree with minmax objective. Discr. Appl. Mathematics\u00a075, 201\u2013216 (1997)","journal-title":"Discr. Appl. Mathematics"},{"key":"8_CR5","doi-asserted-by":"crossref","unstructured":"Awerbuch, B., Betke, M., Rivest, R., Singh, M.: Piecemeal graph learning by a mobile robot. In: Proc. 8th Conf. on Comput. Learning Theory, pp. 321\u2013328 (1995)","DOI":"10.1145\/225298.225337"},{"key":"8_CR6","doi-asserted-by":"crossref","unstructured":"Bender, M.A., Fernandez, A., Ron, D., Sahai, A., Vadhan, S.: The power of a pebble: Exploring and mapping directed graphs. In: STOC 1998. Proc. 30th Ann. Symp. on Theory of Computing, pp. 269\u2013278 (1998)","DOI":"10.1145\/276698.276759"},{"key":"8_CR7","doi-asserted-by":"crossref","unstructured":"Bender, M.A., Slonim, D.: The power of team exploration: Two robots can learn unlabeled directed graphs, Proc. 35th Ann. In: FOCS 1994. Symp. on Foundations of Computer Science, pp. 75\u201385 (1994)","DOI":"10.1109\/SFCS.1994.365703"},{"key":"8_CR8","first-page":"231","volume":"18","author":"M. Betke","year":"1995","unstructured":"Betke, M., Rivest, R., Singh, M.: Piecemeal learning of an unknown environment. Machine Learning\u00a018, 231\u2013254 (1995)","journal-title":"Machine Learning"},{"key":"8_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45061-0_90","volume-title":"Automata, Languages and Programming","author":"M. Cieliebak","year":"2003","unstructured":"Cieliebak, M., Flocchini, P., Prencipe, G., Santoro, N.: Solving the Robots Gathering Problem. In: Baeten, J.C.M., Lenstra, J.K., Parrow, J., Woeginger, G.J. (eds.) ICALP 2003. LNCS, vol.\u00a02719, Springer, Heidelberg (2003)"},{"key":"8_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1007\/978-3-540-27796-5_8","volume-title":"Structural Information and Communication Complexity","author":"R. Cohen","year":"2004","unstructured":"Cohen, R., Peleg, D.: Robot convergence via center-of-gravity algorithms. In: Kralovic, R., S\u00fdkora, O. (eds.) SIROCCO 2004. LNCS, vol.\u00a03104, pp. 79\u201388. Springer, Heidelberg (2004)"},{"key":"8_CR11","series-title":"Lecture Notes in Computer Science","first-page":"744","volume-title":"Algorithms and Computation","author":"J. Czyzowicz","year":"2006","unstructured":"Czyzowicz, J., Gasieniec, L., Pelc, A.: Gathering few fat mobile robots in the plane. In: Asano, T. (ed.) ISAAC 2006. LNCS, vol.\u00a04288, pp. 744\u2013753. Springer, Heidelberg (2006)"},{"key":"8_CR12","doi-asserted-by":"crossref","unstructured":"Das, S., Flocchini, P., Kutten, S., Nayak, A., Santoro, N.: Map construction of unknown graphs by multiple agents. Theoretical Computer Science (to appear 2007)","DOI":"10.1016\/j.tcs.2007.05.011"},{"key":"8_CR13","doi-asserted-by":"crossref","unstructured":"D\u00e9fago, X., Konagaya, A.: Circle formation for oblivious anonymous mobile robots with no common sense of orientation. In: Workshop on Principles of Mobile Computing, pp. 97\u2013104 (2002)","DOI":"10.1145\/584490.584509"},{"key":"8_CR14","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, 265\u2013297 (1999)","journal-title":"Journal of Graph Theory"},{"key":"8_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"374","DOI":"10.1007\/3-540-45749-6_35","volume-title":"Algorithms - ESA 2002","author":"A. Dessmark","year":"2002","unstructured":"Dessmark, A., Pelc, A.: Optimal graph exploration without good maps. In: M\u00f6hring, R.H., Raman, R. (eds.) ESA 2002. LNCS, vol.\u00a02461, pp. 374\u2013386. Springer, Heidelberg (2002)"},{"key":"8_CR16","first-page":"588","volume-title":"SODA 2002","author":"K. Diks","year":"2002","unstructured":"Diks, K., Fraigniaud, P., Kranakis, E., Pelc, A.: Tree exploration with little memory. In: SODA 2002. Proc. 13th Ann. ACM-SIAM Symp. on Discrete Algorithms, pp. 588\u2013597. ACM Press, New York (2002)"},{"key":"8_CR17","first-page":"807","volume-title":"SODA 2001","author":"C.A. Duncan","year":"2001","unstructured":"Duncan, C.A., Kobourov, S.G., Kumar, V.S.A.: Optimal constrained graph exploration. In: SODA 2001. Proc. 12th Ann. ACM-SIAM Symp. on Discrete Algorithms, pp. 807\u2013814. ACM Press, New York (2001)"},{"key":"8_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1007\/11561071_4","volume-title":"Algorithms \u2013 ESA 2005","author":"R. Fleischer","year":"2005","unstructured":"Fleischer, R., Trippen, G.: Exploring an unknown graph efficiently. In: Brodal, G.S., Leonardi, S. (eds.) ESA 2005. LNCS, vol.\u00a03669, pp. 11\u201322. Springer, Heidelberg (2005)"},{"key":"8_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1007\/3-540-46632-0_10","volume-title":"Algorithms and Computations","author":"P. Flocchini","year":"1999","unstructured":"Flocchini, P., Prencipe, G., Santoro, N., Widmayer, P.: Hard tasks for weak robot. In: Aggarwal, A.K., Pandu Rangan, C. (eds.) ISAAC 1999. LNCS, vol.\u00a01741, pp. 93\u2013102. Springer, Heidelberg (1999)"},{"key":"8_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1007\/978-3-540-24698-5_18","volume-title":"LATIN 2004: Theoretical Informatics","author":"P. Fraigniaud","year":"2004","unstructured":"Fraigniaud, P., Gasieniec, L., Kowalski, D., Pelc, A.: Collective tree exploration. In: Farach-Colton, M. (ed.) LATIN 2004. LNCS, vol.\u00a02976, pp. 141\u2013151. Springer, Heidelberg (2004)"},{"key":"8_CR21","doi-asserted-by":"publisher","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.\u00a07, 178\u2013193 (1978)","journal-title":"SIAM J. Comput."},{"key":"8_CR22","unstructured":"Gasieniec, L., Pelc, A., Radzik, T., Zhang, X.: Tree exploration with logarithmic memory. In: SODA 2007. Proc. 18th Annual ACM-SIAM Symp. on Discrete Algorithms, New Orleans, Louisiana, USA (January 2007)"},{"key":"8_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/11940128_74","volume-title":"Algorithms and Computation","author":"R. Klasing","year":"2006","unstructured":"Klasing, R., Markou, E., Pelc, A.: Gathering asynchronous oblivious mobile robots in a ring. In: Asano, T. (ed.) ISAAC 2006. LNCS, vol.\u00a04288, Springer, Heidelberg (2006)"},{"key":"8_CR24","series-title":"Lecture Notes in Computer Science","volume-title":"Mobile Ad-hoc and Sensor Networks","author":"X. Li","year":"2006","unstructured":"Li, X., Santoro, N.: An Integrated self-deployment and coverage maintenance scheme for mobile sensor networks. In: Cao, J., Stojmenovic, I., Jia, X., Das, S.K. (eds.) MSN 2006. LNCS, vol.\u00a04325, Springer, Heidelberg (2006)"},{"key":"8_CR25","doi-asserted-by":"publisher","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. Journal of Algorithms\u00a033, 281\u2013295 (1999)","journal-title":"Journal of Algorithms"},{"key":"8_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"246","DOI":"10.1007\/11429647_20","volume-title":"Structural Information and Communication Complexity","author":"G. Prencipe","year":"2005","unstructured":"Prencipe, G.: On the feasibility of gathering by autonomous mobile robots. In: Pelc, A., Raynal, M. (eds.) SIROCCO 2005. LNCS, vol.\u00a03499, pp. 246\u2013261. Springer, Heidelberg (2005)"},{"key":"8_CR27","doi-asserted-by":"crossref","unstructured":"Prencipe, G., Santoro, N.: Distributed algorithms for mobile robots. In: TCS 2006. Proc. 5th IFIP Int. Conf. on Theoretical Computer Science, pp. 47\u201362 (2006)","DOI":"10.1007\/978-0-387-34735-6_8"},{"key":"8_CR28","doi-asserted-by":"publisher","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.\u00a081, 269 (1997)","journal-title":"Math. Gaz."},{"key":"8_CR29","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1007\/11945529_24","volume-title":"Principles of Distributed Systems","author":"S. Souissi","year":"2006","unstructured":"Souissi, S., D\u00e9fago, X., Yamashita, M.: Gathering asynchronous mobile robots with inaccurate compasses. In: Shvartsman, A.A. (ed.) OPODIS 2006. LNCS, vol.\u00a04305, pp. 333\u2013349. Springer, Heidelberg (2006)"},{"issue":"4","key":"8_CR30","doi-asserted-by":"publisher","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.\u00a028(4), 1347\u20131363 (1999)","journal-title":"SIAM J. Comput."}],"container-title":["Lecture Notes in Computer Science","Principles of Distributed Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-77096-1_8.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,29]],"date-time":"2025-01-29T16:41:23Z","timestamp":1738168883000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-77096-1_8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540770954","9783540770961"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-77096-1_8","relation":{},"subject":[]}}