{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,13]],"date-time":"2026-01-13T21:10:03Z","timestamp":1768338603885,"version":"3.49.0"},"reference-count":45,"publisher":"Oxford University Press (OUP)","issue":"1","license":[{"start":{"date-parts":[[2022,11,20]],"date-time":"2022-11-20T00:00:00Z","timestamp":1668902400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/journals\/pages\/open_access\/funder_policies\/chorus\/standard_publication_model"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2024,1,17]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>We consider the problem of constructing a maximum independent set with mobile myopic luminous robots on a grid network whose size is finite but unknown to the robots. In this setting, the robots enter the grid network one by one from a corner of the grid, and they eventually have to be disseminated on the grid nodes so that the occupied positions form a maximum independent set of the network. We assume that robots are asynchronous, anonymous, silent and they execute the same distributed algorithm. In this paper, we propose two algorithms: The first one assumes that the number of light colors of each robot is three and the visible range is two, but uses the additional assumption that a local edge-labeling exists for each node. To remove this assumption, the second one assumes that the number of light colors of each robot is seven, and that the visible range is three. In both algorithms, the number of movements is $O(n(L+l))$ steps, where $n$ is the number of nodes and $L$ and $l$ are the grid dimensions.<\/jats:p>","DOI":"10.1093\/comjnl\/bxac158","type":"journal-article","created":{"date-parts":[[2022,11,28]],"date-time":"2022-11-28T15:59:43Z","timestamp":1669651183000},"page":"57-77","source":"Crossref","is-referenced-by-count":9,"title":["An Asynchronous Maximum Independent Set Algorithm By Myopic Luminous Robots On Grids"],"prefix":"10.1093","volume":"67","author":[{"given":"Sayaka","family":"Kamei","sequence":"first","affiliation":[{"name":"Graduate School of Advanced Science and Engineering, Hiroshima University , Japan"}]},{"given":"S\u00e9bastien","family":"Tixeuil","sequence":"additional","affiliation":[{"name":"Sorbonne University, CNRS, LIP6, Institut Universitaire de France , Paris, France"}]}],"member":"286","published-online":{"date-parts":[[2022,11,20]]},"reference":[{"key":"2024012011462682000_ref1","doi-asserted-by":"crossref","first-page":"1347","DOI":"10.1137\/S009753979628292X","article-title":"Distributed anonymous mobile robots: Formation of geometric patterns","volume":"28","author":"Suzuki","year":"1999","journal-title":"SIAM Journal on Computing"},{"key":"2024012011462682000_ref2","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-030-11072-7","volume-title":"Distributed Computing by Mobile Entities, Current Research in Moving and Computing","author":"Flocchini","year":"2019"},{"key":"2024012011462682000_ref3","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-030-11072-7","volume-title":"Distributed Computing by Mobile Entities, Current Research in Moving and Computing","author":"Flocchini","year":"2019"},{"key":"2024012011462682000_ref4","volume-title":"Distributed Computing by Mobile Entities, Current Research in Moving and Computing","author":"Cicerone","year":"2019"},{"key":"2024012011462682000_ref5","volume-title":"Distributed Computing by Mobile Entities, Current Research in Moving and Computing","author":"Ilcinkas","year":"2019"},{"key":"2024012011462682000_ref6","volume-title":"Distributed Computing by Mobile Entities, Current Research in Moving and Computing","author":"D\u00e9fago","year":"2019"},{"key":"2024012011462682000_ref7","volume-title":"Distributed Computing by Mobile Entities, Current Research in Moving and Computing","author":"Potop-Butucaru","year":"2019"},{"key":"2024012011462682000_ref8","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1007\/978-3-030-31277-0_7","volume-title":"Networked Systems","author":"Balabonski","year":"2019"},{"key":"2024012011462682000_ref9","doi-asserted-by":"crossref","first-page":"64","DOI":"10.1007\/978-3-642-33536-5_7","volume-title":"Stabilization, Safety, and Security of Distributed Systems","author":"Devismes","year":"2012"},{"key":"2024012011462682000_ref10","doi-asserted-by":"crossref","first-page":"132","DOI":"10.1093\/comjnl\/bxz166","article-title":"Terminating exploration of a grid by an optimal number of asynchronous oblivious robots","volume":"64","author":"Devismes","year":"2020","journal-title":"The Computer Journal"},{"key":"2024012011462682000_ref11","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1007\/978-3-642-25873-2_18","volume-title":"Principles of Distributed Systems","author":"Bonnet","year":"2011"},{"key":"2024012011462682000_ref12","doi-asserted-by":"crossref","first-page":"679","DOI":"10.1142\/S0129054111008295","article-title":"Uniform scattering of autonomous mobile robots in a grid","volume":"22","author":"Barri\u00e8re","year":"2011","journal-title":"International Journal of Foundations of Computer Science"},{"key":"2024012011462682000_ref13","first-page":"183","volume-title":"Proceedings of WALCOM2020","author":"Kshemkalyani","year":"2020"},{"key":"2024012011462682000_ref14","doi-asserted-by":"crossref","first-page":"158","DOI":"10.1016\/j.tcs.2014.06.045","article-title":"Gathering of robots on anonymous grids and trees without multiplicity detection","volume":"610","author":"D\u2019Angelo","year":"2016","journal-title":"Theoretical Computer Science"},{"key":"2024012011462682000_ref15","first-page":"83","volume-title":"Algorithms for Sensor Systems","author":"Adhikary","year":"2018"},{"key":"2024012011462682000_ref16","doi-asserted-by":"crossref","first-page":"213","DOI":"10.1016\/j.tcs.2020.02.016","article-title":"Arbitrary pattern formation on infinite grid by asynchronous oblivious robots","volume":"815","author":"Bose","year":"2020","journal-title":"Theoretical Computer Science"},{"key":"2024012011462682000_ref17","first-page":"1051","volume-title":"Proceedings of IPDPS2020.","author":"Hector","year":"2020"},{"key":"2024012011462682000_ref18","first-page":"335","volume-title":"Computer Safety, Reliability, and Security","author":"Datta","year":"2013"},{"key":"2024012011462682000_ref19","doi-asserted-by":"crossref","first-page":"86","DOI":"10.1016\/j.tcs.2012.07.004","article-title":"Gathering asynchronous oblivious agents with local vision in regular bipartite graphs","volume":"509","author":"Guilbault","year":"2013","journal-title":"Theoretical Computer Science"},{"key":"2024012011462682000_ref20","first-page":"46","volume-title":"Proceedings of SRDSW2014.","author":"Kamei","year":"2014"},{"key":"2024012011462682000_ref21","first-page":"291","volume-title":"Algorithms for Sensor Systems","author":"Viglietta","year":"2013"},{"key":"2024012011462682000_ref22","doi-asserted-by":"crossref","first-page":"171","DOI":"10.1016\/j.tcs.2015.09.018","article-title":"Autonomous mobile robots with lights","volume":"609","author":"Das","year":"2016","journal-title":"Theoretical Computer Science"},{"key":"2024012011462682000_ref23","first-page":"1","volume-title":"Proceedings of ICDCN2018.","author":"Heriban","year":"2018"},{"key":"2024012011462682000_ref24","doi-asserted-by":"crossref","first-page":"301","DOI":"10.1007\/978-3-030-03232-6_20","volume-title":"Stabilization, Safety, and Security of Distributed Systems","author":"Ooshita","year":"2018"},{"key":"2024012011462682000_ref25","doi-asserted-by":"crossref","first-page":"256","DOI":"10.1007\/978-3-030-34992-9_20","volume-title":"Stabilization, Safety, and Security of Distributed Systems","author":"Nagahama","year":"2019"},{"key":"2024012011462682000_ref26","first-page":"129","volume-title":"Networked Systems","author":"Bramas","year":"2020"},{"key":"2024012011462682000_ref27","first-page":"586","volume-title":"Proceedings of IPDPSW2021.","author":"Nagahama","year":"2021"},{"key":"2024012011462682000_ref28","first-page":"27:1","volume-title":"Proceedings of OPODIS 2019","author":"Kamei","year":"2019"},{"key":"2024012011462682000_ref29","article-title":"A survey on pattern formation of autonomous mobile robots: asynchrony, obliviousness and visibility","volume":"473","author":"Yamauchi","year":"2013","journal-title":"Journal of Physics: Conference Series"},{"key":"2024012011462682000_ref30","doi-asserted-by":"crossref","first-page":"175","DOI":"10.1142\/S0129626409000146","article-title":"Scatter of robots","volume":"19","author":"Dieudonn\u00e9","year":"2009","journal-title":"Parallel Processing Letters"},{"key":"2024012011462682000_ref31","doi-asserted-by":"crossref","first-page":"431","DOI":"10.1016\/j.ipl.2010.04.006","article-title":"The cost of probabilistic agreement in oblivious robot networks","volume":"110","author":"Cl\u00e9ment","year":"2010","journal-title":"Information Processing Letters"},{"key":"2024012011462682000_ref32","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1142\/S0129054117500083","article-title":"The random bit complexity of mobile robots scattering","volume":"28","author":"Bramas","year":"2017","journal-title":"International Journal of Foundations of Computer Science"},{"key":"2024012011462682000_ref33","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1016\/j.tcs.2008.02.007","article-title":"Local spreading algorithms for autonomous robot systems","volume":"399","author":"Cohen","year":"2008","journal-title":"Theoretical Computer Science"},{"key":"2024012011462682000_ref34","volume-title":"Encyclopedia of Algorithms","author":"Flocchini","year":"2016"},{"key":"2024012011462682000_ref35","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1016\/j.tcs.2008.03.006","article-title":"Self-deployment of mobile sensors on a ring","volume":"402","author":"Flocchini","year":"2008","journal-title":"Theoretical Computer Science"},{"key":"2024012011462682000_ref36","doi-asserted-by":"crossref","first-page":"1038","DOI":"10.1016\/j.comcom.2011.09.008","article-title":"Biconnecting a network of mobile robots using virtual angular forces","volume":"35","author":"Casteigts","year":"2012","journal-title":"Computer Communications"},{"key":"2024012011462682000_ref37","first-page":"235","volume-title":"Structural Information and Communication Complexity","author":"Hesari","year":"2014"},{"key":"2024012011462682000_ref38","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1007\/978-3-030-64348-5_17","volume-title":"Stabilization, Safety, and Security of Distributed Systems","author":"Poudel","year":"2020"},{"key":"2024012011462682000_ref39","volume-title":"Algorithmic Foundations of Robotics V","author":"Hsiang","year":"2004"},{"key":"2024012011462682000_ref40","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1007\/978-3-540-92862-1_11","volume-title":"Algorithmic Aspects of Wireless Sensor Networks","author":"Barrameda","year":"2008"},{"key":"2024012011462682000_ref41","first-page":"228","volume-title":"Algorithms for Sensor Systems","author":"Barrameda","year":"2013"},{"key":"2024012011462682000_ref42","first-page":"155","volume-title":"Algorithms for Sensor Systems","author":"Hideg","year":"2017"},{"key":"2024012011462682000_ref43","first-page":"193","volume-title":"Algorithms for Sensor Systems","author":"Hideg","year":"2018"},{"key":"2024012011462682000_ref44","doi-asserted-by":"crossref","first-page":"108","DOI":"10.1007\/978-3-030-62401-9_8","volume-title":"Algorithms for Sensor Systems","author":"Hideg","year":"2020"},{"key":"2024012011462682000_ref45","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1016\/j.entcs.2016.03.012","article-title":"Synchronous robots vs asynchronous lights-enhanced robots on graphs","volume":"322","author":"D\u2019Emidio","year":"2016","journal-title":"Electronic Notes in Theoretical Computer Science"}],"container-title":["The Computer Journal"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/comjnl\/article-pdf\/67\/1\/57\/56167790\/bxac158.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/comjnl\/article-pdf\/67\/1\/57\/56167790\/bxac158.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,1,20]],"date-time":"2024-01-20T11:46:55Z","timestamp":1705751215000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/comjnl\/article\/67\/1\/57\/6834177"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,11,20]]},"references-count":45,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2022,11,20]]},"published-print":{"date-parts":[[2024,1,17]]}},"URL":"https:\/\/doi.org\/10.1093\/comjnl\/bxac158","relation":{},"ISSN":["0010-4620","1460-2067"],"issn-type":[{"value":"0010-4620","type":"print"},{"value":"1460-2067","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2024,1]]},"published":{"date-parts":[[2022,11,20]]}}}