{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,17]],"date-time":"2025-11-17T21:35:25Z","timestamp":1763415325131},"reference-count":33,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2014,5,31]],"date-time":"2014-05-31T00:00:00Z","timestamp":1401494400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2015,8]]},"DOI":"10.1007\/s00453-014-9892-6","type":"journal-article","created":{"date-parts":[[2014,5,30]],"date-time":"2014-05-30T19:06:32Z","timestamp":1401476792000},"page":"1055-1096","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":28,"title":["Computing on Rings by Oblivious Robots: A Unified Approach for Different Tasks"],"prefix":"10.1007","volume":"72","author":[{"given":"Gianlorenzo","family":"D\u2019Angelo","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gabriele","family":"Di Stefano","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alfredo","family":"Navarra","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nicolas","family":"Nisse","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Karol","family":"Suchan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2014,5,31]]},"reference":[{"issue":"2","key":"9892_CR1","doi-asserted-by":"crossref","first-page":"17:1","DOI":"10.1145\/1921659.1921663","volume":"7","author":"C Amb\u00fchl","year":"2011","unstructured":"Amb\u00fchl, C., G\u0105sieniec, L., Pelc, A., Radzik, T., Zhang, X.: Tree exploration with logarithmic memory. ACM Trans. Algorithms 7(2), 17:1\u201317:21 (2011)","journal-title":"ACM Trans. Algorithms"},{"issue":"2","key":"9892_CR2","doi-asserted-by":"crossref","first-page":"98","DOI":"10.1016\/j.ipl.2008.08.011","volume":"109","author":"R Baldoni","year":"2008","unstructured":"Baldoni, R., Bonnet, F., Milani, A., Raynal, M.: Anonymous graph exploration without collision by mobile robots. Inf. Process. Lett. 109(2), 98\u2013103 (2008)","journal-title":"Inf. Process. Lett."},{"key":"9892_CR3","doi-asserted-by":"crossref","unstructured":"Baldoni, R., Bonnet, F., Milani, A., Raynal, M.: On the solvability of anonymous partial grids exploration by mobile robots. In: Proceedings of the 12th International Conference On Principles Of Distributed Systems (OPODIS). volume 5401 of Lecture Notes in Computer Science, pp. 428\u2013445. Springer (2008)","DOI":"10.1007\/978-3-540-92221-6_27"},{"key":"9892_CR4","doi-asserted-by":"crossref","unstructured":"Bampas, E., Czyzowicz, J., G\u0105sieniec, L., Ilcinkas, D., Labourel, A.: Almost optimal asynchronous rendezvous in infinite multidimensional grids. In: Proceedings of the 24th International Symposium on Distributed Computing (DISC). volume 6343 of Lecture Notes in Computer Science, pp. 297\u2013311 (2010)","DOI":"10.1007\/978-3-642-15763-9_28"},{"issue":"2","key":"9892_CR5","doi-asserted-by":"crossref","first-page":"239","DOI":"10.1016\/0196-6774(91)90003-H","volume":"12","author":"D Bienstock","year":"1991","unstructured":"Bienstock, D., Seymour, P.D.: Monotonicity in graph searching. J. Algorithms 12(2), 239\u2013245 (1991)","journal-title":"J. Algorithms"},{"key":"9892_CR6","doi-asserted-by":"crossref","unstructured":"Blin, L., Milani, A., Potop-Butucaru, M., Tixeuil, S.: Exclusive perpetual ring exploration without chirality. In: Proceedings of the 24th International Symposium on Distributed Computing (DISC). volume 6343 of Lecture Notes in Computer Science, pp. 312\u2013327 (2010)","DOI":"10.1007\/978-3-642-15763-9_29"},{"key":"9892_CR7","doi-asserted-by":"crossref","unstructured":"Blin, L., Burman, J., Nisse, N.: Exclusive graph searching. In: Proceedings of the 21st European Symposium on Algorithms (ESA). volume 8125 of Lecture Notes in Computer Science, pp. 181\u2013192. Springer (2013)","DOI":"10.1007\/978-3-642-40450-4_16"},{"key":"9892_CR8","doi-asserted-by":"crossref","unstructured":"Bonnet, F., Milani, A., Potop-Butucaru, M., Tixeuil, S.: Asynchronous exclusive perpetual grid exploration without sense of direction. In: Proceedings of the 15th International Conference On Principles Of Distributed Systems (OPODIS). volume 7109 of Lecture Notes in Computer Science, pp. 251\u2013265. Springer (2011)","DOI":"10.1007\/978-3-642-25873-2_18"},{"key":"9892_CR9","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1016\/j.tcs.2012.10.056","volume":"509","author":"P Brandes","year":"2013","unstructured":"Brandes, P., Degener, B., Kempkes, B., Meyer auf der Heide, F.: Energy-efficient strategies for building short chains of mobile robots locally. Theor. Comput. Sci. 509, 97\u2013112 (2013)","journal-title":"Theor. Comput. Sci."},{"issue":"11","key":"9892_CR10","doi-asserted-by":"crossref","first-page":"431","DOI":"10.1016\/j.ipl.2010.04.006","volume":"110","author":"J Cl\u00e9ment","year":"2010","unstructured":"Cl\u00e9ment, J., D\u00e9fago, X., Potop-Butucaru, M.G., Izumi, T., Messika, S.: The cost of probabilistic agreement in oblivious robot networks. Inf. Process. Lett. 110(11), 431\u2013438 (2010)","journal-title":"Inf. Process. Lett."},{"issue":"4","key":"9892_CR11","doi-asserted-by":"crossref","first-page":"42:1","DOI":"10.1145\/1383369.1383373","volume":"4","author":"R Cohen","year":"2008","unstructured":"Cohen, R., Fraigniaud, P., Ilcinkas, D., Korman, A., Peleg, D.: Label-guided graph exploration by a finite automaton. ACM Trans. Algorithms 4(4), 42:1\u201342:18 (2008)","journal-title":"ACM Trans. Algorithms"},{"issue":"6\u20137","key":"9892_CR12","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., G\u0105sieniec, L., Pelc, A.: Gathering few fat mobile robots in the plane. Theor. Comput. Sci. 410(6\u20137), 481\u2013499 (2009)","journal-title":"Theor. Comput. Sci."},{"key":"9892_CR13","doi-asserted-by":"crossref","unstructured":"D\u2019Angelo, G., Di Stefano, G., Navarra, A.: Gathering of six robots on anonymous symmetric rings. In: Proceedings of the 18th International Colloquium on Structural Information and Commnication Complexity (SIROCCO). volume 6796 of Lecture Notes in Computer Science, pp. 174\u2013185 (2011)","DOI":"10.1007\/978-3-642-22212-2_16"},{"key":"9892_CR14","doi-asserted-by":"crossref","unstructured":"D\u2019Angelo, G., Di Stefano, G., Klasing, R., Navarra, A.: Gathering of robots on anonymous grids without multiplicity detection. In: Proceedings of the 19th International Colloquium on Structural Information and Communication Complexity (SIROCCO). volume 7355 of Lecture Notes in Computer Science, pp. 327\u2013338 (2012)","DOI":"10.1007\/978-3-642-31104-8_28"},{"key":"9892_CR15","doi-asserted-by":"crossref","unstructured":"D\u2019Angelo, G., Di Stefano, G., Navarra, A.: How to gather asynchronous oblivious robots on anonymous rings. In: Proceedings of the 26th International Symposium on Distributed Computing (DISC). volume 7611 of Lecture Notes in Computer Science, pp. 330\u2013344 (2012)","DOI":"10.1007\/978-3-642-33651-5_23"},{"key":"9892_CR16","doi-asserted-by":"crossref","first-page":"197","DOI":"10.1007\/978-1-4614-6825-7_13","volume-title":"Search Theory: A Game Theoretic Perspective","author":"G D\u2019Angelo","year":"2013","unstructured":"D\u2019Angelo, G., Di Stefano, G., Navarra, A.: Gathering asynchronous and oblivious robots on basic graph topologies under the look-compute-move model. In: Alpern, S., Fokkink, R., G\u0105sieniec, L., Lindelauf, R., Subrahmanian, V. (eds.) Search Theory: A Game Theoretic Perspective, pp. 197\u2013222. Springer, Berlin (2013)"},{"key":"9892_CR17","doi-asserted-by":"crossref","unstructured":"D\u2019Angelo, G., Di Stefano, G., Navarra, A., Nisse, N., Suchan, K.: A unified approach for different tasks on rings in robot-based computing systems. In: Proceedings of the 15th IEEE IPDPS Workshop on Advances in Parallel and Distributed Computing Models (APDCM), pp. 667\u2013676 (2013)","DOI":"10.1109\/IPDPSW.2013.89"},{"key":"9892_CR18","doi-asserted-by":"crossref","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). volume 5869 of Lecture Notes in Computer Science, pp. 195\u2013208 (2009)","DOI":"10.1007\/978-3-642-11476-2_16"},{"issue":"1","key":"9892_CR19","doi-asserted-by":"crossref","first-page":"175","DOI":"10.1142\/S0129626409000146","volume":"19","author":"Y Dieudonne","year":"2009","unstructured":"Dieudonne, Y., Petit, F.: Scatter of robots. Parallel Process. Lett. 19(1), 175\u2013184 (2009)","journal-title":"Parallel Process. Lett."},{"issue":"14\u201315","key":"9892_CR20","doi-asserted-by":"crossref","first-page":"1583","DOI":"10.1016\/j.tcs.2010.01.007","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(14\u201315), 1583\u20131598 (2010)","journal-title":"Theor. Comput. Sci."},{"key":"9892_CR21","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-031-02008-7","volume-title":"Distributed Computing by Oblivious Mobile Robots","author":"P Flocchini","year":"2012","unstructured":"Flocchini, P., Prencipe, G., Santoro, N.: Distributed Computing by Oblivious Mobile Robots. Morgan and Claypool, San Rafael (2012)"},{"key":"9892_CR22","doi-asserted-by":"crossref","first-page":"562","DOI":"10.1007\/s00453-011-9611-5","volume":"65","author":"P Flocchini","year":"2013","unstructured":"Flocchini, P., Ilcinkas, D., Pelc, A., Santoro, N.: Computing without communicating: ring exploration by asynchronous oblivious robots. Algorithmica 65, 562\u2013583 (2013)","journal-title":"Algorithmica"},{"issue":"3","key":"9892_CR23","doi-asserted-by":"crossref","first-page":"236","DOI":"10.1016\/j.tcs.2008.02.040","volume":"399","author":"FV Fomin","year":"2008","unstructured":"Fomin, F.V., Thilikos, D.M.: An annotated bibliography on guaranteed graph searching. Theoret. Comput. Sci. 399(3), 236\u2013245 (2008)","journal-title":"Theoret. Comput. Sci."},{"issue":"2","key":"9892_CR24","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1007\/s00446-009-0089-1","volume":"22","author":"D Ilcinkas","year":"2009","unstructured":"Ilcinkas, D., Nisse, N., Soguet, D.: The cost of monotonicity in distributed graph searching. Distrib. Comput. 22(2), 117\u2013127 (2009)","journal-title":"Distrib. Comput."},{"key":"9892_CR25","doi-asserted-by":"crossref","unstructured":"Izumi, T., Izumi, T., Kamei, S., Ooshita, F.: Mobile robots gathering algorithm with local weak multiplicity in rings. In: Proceedings of the 17th International Colloquium on Structural Information and Communication Complexity (SIROCCO). volume 6058 of Lecture Notes in Computer Science, pp. 101\u2013113 (2010)","DOI":"10.1007\/978-3-642-13284-1_9"},{"issue":"4","key":"9892_CR26","doi-asserted-by":"crossref","first-page":"716","DOI":"10.1109\/TPDS.2012.212","volume":"24","author":"T Izumi","year":"2013","unstructured":"Izumi, T., Izumi, T., Kamei, S., Ooshita, F.: Feasibility of polynomial-time randomized gathering for oblivious mobile robots. IEEE Trans. Parallel Distrib. Syst. 24(4), 716\u2013723 (2013)","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"key":"9892_CR27","doi-asserted-by":"crossref","unstructured":"Kamei, S., Lamani, A., Ooshita, F., Tixeuil, S.: Asynchronous mobile robot gathering from symmetric configurations. In: Proceedings of the 18th International Colloquium on Structural Information and Communication Complexity (SIROCCO). volume 6796 of Lecture Notes in Computer Science, pp. 150\u2013161 (2011)","DOI":"10.1007\/978-3-642-22212-2_14"},{"key":"9892_CR28","doi-asserted-by":"crossref","unstructured":"Kamei, S., Lamani, A., Ooshita, F., Tixeuil, S.: Gathering an even number of robots in an odd ring without global multiplicity detection. In: Proceedings of the 37th International Symposium on Mathematical Foundations of Computer Science (MFCS). volume 7464 of Lecture Notes in Computer Science, pp. 542\u2013553 (2012)","DOI":"10.1007\/978-3-642-32589-2_48"},{"key":"9892_CR29","doi-asserted-by":"crossref","unstructured":"Kempkes, B., Kling, P., Meyer auf der Heide, F.: Optimal and competitive runtime bounds for continuous, local gathering of mobile robots. In: Proceedings of the 24th Annual ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pp. 18\u201326. ACM (2012)","DOI":"10.1145\/2312005.2312009"},{"key":"9892_CR30","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":"9892_CR31","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."},{"issue":"3","key":"9892_CR32","doi-asserted-by":"crossref","first-page":"331","DOI":"10.1002\/net.21453","volume":"59","author":"A Pelc","year":"2012","unstructured":"Pelc, A.: Deterministic rendezvous in networks: a comprehensive survey. Networks 59(3), 331\u2013347 (2012)","journal-title":"Networks"},{"key":"9892_CR33","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."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-014-9892-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-014-9892-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-014-9892-6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,7,13]],"date-time":"2023-07-13T20:42:13Z","timestamp":1689280933000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-014-9892-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,5,31]]},"references-count":33,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2015,8]]}},"alternative-id":["9892"],"URL":"https:\/\/doi.org\/10.1007\/s00453-014-9892-6","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,5,31]]}}}