{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,16]],"date-time":"2025-07-16T13:12:09Z","timestamp":1752671529399,"version":"3.40.3"},"publisher-location":"Cham","reference-count":32,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783031099922"},{"type":"electronic","value":"9783031099939"}],"license":[{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2022]]},"DOI":"10.1007\/978-3-031-09993-9_11","type":"book-chapter","created":{"date-parts":[[2022,6,24]],"date-time":"2022-06-24T20:12:42Z","timestamp":1656101562000},"page":"191-211","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Dispersion of\u00a0Mobile Robots on\u00a0Directed Anonymous Graphs"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9492-9894","authenticated-orcid":false,"given":"Giuseppe F.","family":"Italiano","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2862-2795","authenticated-orcid":false,"given":"Debasish","family":"Pattanayak","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4930-4609","authenticated-orcid":false,"given":"Gokarna","family":"Sharma","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,6,25]]},"reference":[{"doi-asserted-by":"crossref","unstructured":"Albers, S., Henzinger, M.R.: Exploring unknown environments. In: STOC, pp. 416\u2013425. ACM (1997)","key":"11_CR1","DOI":"10.1145\/258533.258630"},{"doi-asserted-by":"crossref","unstructured":"Augustine, J., Moses Jr., W.K.: Dispersion of mobile robots: a study of memory-time trade-offs. In: ICDCN, pp. 1:1\u20131:10 (2018)","key":"11_CR2","DOI":"10.1145\/3154273.3154293"},{"doi-asserted-by":"crossref","unstructured":"Bampas, E., Gasieniec, L., Hanusse, N., Ilcinkas, D., Klasing, R., Kosowski, A.: Euler tour lock-in problem in the rotor-router model: I choose pointers and you choose port numbers. In: DISC, pp. 423\u2013435 (2009)","key":"11_CR3","DOI":"10.1007\/978-3-642-04355-0_44"},{"doi-asserted-by":"crossref","unstructured":"Barriere, L., Flocchini, P., Mesa-Barrameda, E., Santoro, N.: Uniform scattering of autonomous mobile robots in a grid. In: IPDPS, pp. 1\u20138 (2009)","key":"11_CR4","DOI":"10.1109\/IPDPS.2009.5160871"},{"doi-asserted-by":"crossref","unstructured":"Bender, M.A., Fern\u00e1ndez, A., Ron, D., Sahai, A., Vadhan, S.P.: The power of a pebble: exploring and mapping directed graphs. In: STOC, pp. 269\u2013278 (1998)","key":"11_CR5","DOI":"10.1145\/276698.276759"},{"doi-asserted-by":"crossref","unstructured":"Bender, M.A., Slonim, D.K.: The power of team exploration: two robots can learn unlabeled directed graphs. In: FOCS, pp. 75\u201385 (1994)","key":"11_CR6","DOI":"10.1109\/SFCS.1994.365703"},{"doi-asserted-by":"crossref","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)","key":"11_CR7","DOI":"10.1145\/1383369.1383373"},{"issue":"2","key":"11_CR8","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1016\/0743-7315(89)90021-X","volume":"7","author":"G Cybenko","year":"1989","unstructured":"Cybenko, G.: Dynamic load balancing for distributed memory multiprocessors. J. Parallel Distrib. Comput. 7(2), 279\u2013301 (1989)","journal-title":"J. Parallel Distrib. Comput."},{"doi-asserted-by":"crossref","unstructured":"Dereniowski, D., Disser, Y., Kosowski, A., Pajak, D., Uzna\u0144ski, P.: Fast collaborative graph exploration. Inf. Comput. 243(C), 37\u201349 (2015)","key":"11_CR9","DOI":"10.1016\/j.ic.2014.12.005"},{"issue":"8\u201310","key":"11_CR10","doi-asserted-by":"publisher","first-page":"783","DOI":"10.1016\/j.tcs.2010.11.023","volume":"412","author":"Y Elor","year":"2011","unstructured":"Elor, Y., Bruckstein, A.M.: Uniform multi-agent deployment on a ring. Theor. Comput. Sci. 412(8\u201310), 783\u2013795 (2011)","journal-title":"Theor. Comput. Sci."},{"doi-asserted-by":"crossref","unstructured":"Flocchini, P., Prencipe, G., Santoro, N.: Distributed Computing by Oblivious Mobile Robots. Morgan & Claypool Publishers, Synthesis Lectures on Distributed Computing Theory (2012)","key":"11_CR11","DOI":"10.1007\/978-3-031-02008-7"},{"doi-asserted-by":"publisher","unstructured":"Flocchini, P., Prencipe, G., Santoro, N.: Distributed Computing by Mobile Entities, Theoretical Computer Science and General Issues, vol. 1. Springer (2019). https:\/\/doi.org\/10.1007\/978-3-030-11072-7","key":"11_CR12","DOI":"10.1007\/978-3-030-11072-7"},{"key":"11_CR13","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1016\/j.tcs.2015.11.017","volume":"655","author":"K Foerster","year":"2016","unstructured":"Foerster, K., Wattenhofer, R.: Lower and upper competitive bounds for online directed graph exploration. Theor. Comput. Sci. 655, 15\u201329 (2016)","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"11_CR14","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.R., Pelc, A.: Collective tree exploration. Networks 48(3), 166\u2013177 (2006)","journal-title":"Networks"},{"issue":"2\u20133","key":"11_CR15","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1016\/j.tcs.2005.07.014","volume":"345","author":"P Fraigniaud","year":"2005","unstructured":"Fraigniaud, P., Ilcinkas, D., Peer, G., Pelc, A., Peleg, D.: Graph exploration by a finite automaton. Theor. Comput. Sci. 345(2\u20133), 331\u2013344 (2005)","journal-title":"Theor. Comput. Sci."},{"doi-asserted-by":"crossref","unstructured":"Hsiang, T.R., Arkin, E.M., Bender, M.A., Fekete, S., Mitchell, J.S.B.: Online dispersion algorithms for swarms of robots. In: SoCG, pp. 382\u2013383 (2003)","key":"11_CR16","DOI":"10.1145\/777792.777854"},{"doi-asserted-by":"crossref","unstructured":"Hsiang, T., Arkin, E.M., Bender, M.A., Fekete, S.P., Mitchell, J.S.B.: Algorithms for rapidly dispersing robot swarms in unknown environments. In: WAFR, pp. 77\u201394 (2002)","key":"11_CR17","DOI":"10.1007\/978-3-540-45058-0_6"},{"doi-asserted-by":"crossref","unstructured":"Kshemkalyani, A.D., Ali, F.: Fast graph exploration by a mobile robot. In: AIKE, pp. 115\u2013118 (2018)","key":"11_CR18","DOI":"10.1109\/AIKE.2018.00025"},{"doi-asserted-by":"crossref","unstructured":"Kshemkalyani, A.D., Ali, F.: Efficient dispersion of mobile robots on graphs. In: ICDCN, pp. 218\u2013227 (2019)","key":"11_CR19","DOI":"10.1145\/3288599.3288610"},{"doi-asserted-by":"crossref","unstructured":"Kshemkalyani, A.D., Molla, A.R., Sharma, G.: Fast dispersion of mobile robots on arbitrary graphs. In: ALGOSENSORS, pp. 23\u201340 (2019)","key":"11_CR20","DOI":"10.1007\/978-3-030-34405-4_2"},{"doi-asserted-by":"crossref","unstructured":"Kshemkalyani, A.D., Molla, A.R., Sharma, G.: Dispersion of mobile robots in the global communication model. In: ICDCN, pp. 12:1\u201312:10 (2020)","key":"11_CR21","DOI":"10.1145\/3369740.3369775"},{"doi-asserted-by":"crossref","unstructured":"Kshemkalyani, A.D., Molla, A.R., Sharma, G.: Dispersion of mobile robots on grids. In: WALCOM, pp. 183\u2013197 (2020)","key":"11_CR22","DOI":"10.1007\/978-3-030-39881-1_16"},{"doi-asserted-by":"crossref","unstructured":"Kshemkalyani, A.D., Molla, A.R., Sharma, G.: Efficient dispersion of mobile robots on dynamic graphs. In: ICDCS, pp. 732\u2013742 (2020)","key":"11_CR23","DOI":"10.1109\/ICDCS47774.2020.00100"},{"doi-asserted-by":"crossref","unstructured":"Kshemkalyani, A.D., Sharma, G.: Near-optimal dispersion on arbitrary anonymous graphs. CoRR (2021)","key":"11_CR24","DOI":"10.2139\/ssrn.4282040"},{"key":"11_CR25","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1016\/j.ipl.2017.06.010","volume":"127","author":"A Menc","year":"2017","unstructured":"Menc, A., Pajak, D., Uznanski, P.: Time and space optimality of rotor-router graph exploration. Inf. Process. Lett. 127, 17\u201320 (2017)","journal-title":"Inf. Process. Lett."},{"doi-asserted-by":"crossref","unstructured":"Molla, A.R., Jr., W.K.M.: Dispersion of mobile robots: The power of randomness. In: TAMC, pp. 481\u2013500 (2019)","key":"11_CR26","DOI":"10.1007\/978-3-030-14812-6_30"},{"doi-asserted-by":"crossref","unstructured":"Molla, A.R., Mondal, K., Jr., W.K.M.: Efficient dispersion on an anonymous ring in the presence of weak byzantine robots. In: ALGOSENSORS, pp. 154\u2013169 (2020)","key":"11_CR27","DOI":"10.1007\/978-3-030-62401-9_11"},{"doi-asserted-by":"crossref","unstructured":"Molla, A.R., Mondal, K., Jr., W.K.M.: Byzantine dispersion on graphs. In: IPDPS, pp. 942\u2013951. IEEE (2021)","key":"11_CR28","DOI":"10.1109\/IPDPS49936.2021.00103"},{"doi-asserted-by":"crossref","unstructured":"Pattanayak, D., Sharma, G., Mandal, P.S.: Dispersion of mobile robots tolerating faults. In: ICDCN, pp. 133\u2013138 (2021)","key":"11_CR29","DOI":"10.1145\/3427477.3429464"},{"doi-asserted-by":"crossref","unstructured":"Poudel, P., Sharma, G.: Time-optimal uniform scattering in a grid. In: ICDCN, pp. 228\u2013237 (2019)","key":"11_CR30","DOI":"10.1145\/3288599.3288622"},{"doi-asserted-by":"crossref","unstructured":"Shibata, M., Mega, T., Ooshita, F., Kakugawa, H., Masuzawa, T.: Uniform deployment of mobile agents in asynchronous rings. In: PODC, pp. 415\u2013424 (2016)","key":"11_CR31","DOI":"10.1145\/2933057.2933093"},{"doi-asserted-by":"crossref","unstructured":"Shintaku, T., Sudo, Y., Kakugawa, H., Masuzawa, T.: Efficient dispersion of mobile agents without global knowledge. In: SSS, pp. 280\u2013294 (2020)","key":"11_CR32","DOI":"10.1007\/978-3-030-64348-5_22"}],"container-title":["Lecture Notes in Computer Science","Structural Information and Communication Complexity"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-09993-9_11","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,27]],"date-time":"2024-09-27T19:27:25Z","timestamp":1727465245000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-09993-9_11"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022]]},"ISBN":["9783031099922","9783031099939"],"references-count":32,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-09993-9_11","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2022]]},"assertion":[{"value":"25 June 2022","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"SIROCCO","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Colloquium on Structural Information and Communication Complexity","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Paderborn","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Germany","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2022","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"27 June 2022","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"29 June 2022","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"29","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"sirocco2022","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/sirocco2022.cs.uni-paderborn.de\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}