{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,15]],"date-time":"2026-01-15T06:57:13Z","timestamp":1768460233037,"version":"3.49.0"},"publisher-location":"New York, NY, USA","reference-count":28,"publisher":"ACM","license":[{"start":{"date-parts":[[2025,1,4]],"date-time":"2025-01-04T00:00:00Z","timestamp":1735948800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"Natural Sciences and Engineering Research Council of Canada (NSERC)","award":["Discovery grant 2018-03899"],"award-info":[{"award-number":["Discovery grant 2018-03899"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2025,1,4]]},"DOI":"10.1145\/3700838.3700858","type":"proceedings-article","created":{"date-parts":[[2025,1,2]],"date-time":"2025-01-02T12:58:12Z","timestamp":1735822692000},"page":"115-124","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Deterministic Collision-Free Exploration of Unknown Anonymous Graphs"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4551-0613","authenticated-orcid":false,"given":"Subhash","family":"Bhagat","sequence":"first","affiliation":[{"name":"Department of Mathematics, Indian Institute of Technology Jodhpur, Jodhpur, Rajasthan, India"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0598-1218","authenticated-orcid":false,"given":"Andrzej","family":"Pelc","sequence":"additional","affiliation":[{"name":"Departement d'informatique, Universite du Quebec en Outaouais (UQO), Gatineau, Quebec, Canada"}]}],"member":"320","published-online":{"date-parts":[[2025,1,4]]},"reference":[{"key":"e_1_3_3_1_2_2","doi-asserted-by":"crossref","unstructured":"D. Adamson N. Flaherty I. Potapov P. Spirakis Brief announcement: Collision-free robot scheduling Proc. 3rd Symp. on Algorithmic Foundations of Dynamic Networks (SAND 2024) 22:1-22:5.","DOI":"10.2139\/ssrn.5007260"},{"key":"e_1_3_3_1_3_2","doi-asserted-by":"crossref","unstructured":"S. Albers and M. R. Henzinger Exploring unknown environments SIAM Journal on Computing 29 (2000) 1164-1188.","DOI":"10.1137\/S009753979732428X"},{"key":"e_1_3_3_1_4_2","doi-asserted-by":"crossref","unstructured":"R. Aleliunas R. Karp R. Lipton L. Lovasz C. Rackoff Random walks universal traversal sequences and the complexity of maze problems Proc. 20th Annual IEEE Symposium on Foundations of Computer Science (FOCS 1979) 218-223.","DOI":"10.1109\/SFCS.1979.34"},{"key":"e_1_3_3_1_5_2","doi-asserted-by":"crossref","unstructured":"Baruch Awerbuch Margrit Betke Ronald L. Rivest Mona Singh: Piecemeal Graph Exploration by a Mobile Robot. Inf. Comput. 152 (1999) 155-172.","DOI":"10.1006\/inco.1999.2795"},{"key":"e_1_3_3_1_6_2","doi-asserted-by":"crossref","unstructured":"E. Bar-Eli P. Berman A. Fiat and R. Yan On-line navigation in a room Journal of Algorithms 17 (1994) 319-341.","DOI":"10.1006\/jagm.1994.1039"},{"key":"e_1_3_3_1_7_2","doi-asserted-by":"crossref","unstructured":"Michael A. Bender Antonio Fern\u00e1ndez Dana Ron Amit Sahai Salil P. Vadhan: The Power of a Pebble: Exploring and Mapping Directed Graphs. Inf. Comput. 176 (2002) 1-21.","DOI":"10.1006\/inco.2001.3081"},{"key":"e_1_3_3_1_8_2","doi-asserted-by":"crossref","unstructured":"M.A. Bender and D. Slonim The power of team exploration: Two robots can learn unlabeled directed graphs Proc. 35th Ann. Symp. on Foundations of Computer Science (FOCS 1994) 75-85.","DOI":"10.1109\/SFCS.1994.365703"},{"key":"e_1_3_3_1_9_2","doi-asserted-by":"crossref","unstructured":"M. Betke R. Rivest and M. Singh Piecemeal learning of an unknown environment Machine Learning 18 (1995) 231-254.","DOI":"10.1007\/BF00993411"},{"key":"e_1_3_3_1_10_2","doi-asserted-by":"crossref","unstructured":"A. Blum P. Raghavan and B. Schieber Navigating in unfamiliar geometric terrain SIAM Journal on Computing 26 (1997) 110-137.","DOI":"10.1137\/S0097539791194931"},{"key":"e_1_3_3_1_11_2","doi-asserted-by":"crossref","unstructured":"J. Chalopin S. Das A. Kosowski Constructing a map of an anonymous graph: Applications of universal sequences Proc. 14th International Conference on Principles of Distributed Systems (OPODIS 2010) 119-134.","DOI":"10.1007\/978-3-642-17653-1_10"},{"key":"e_1_3_3_1_12_2","doi-asserted-by":"crossref","unstructured":"J. Czyzowicz D.Dereniowski L. Gasieniec R. Klasing A. Kosowski Dominik Pajak Collision-free network exploration. J. Comput. Syst. Sci. 86 (2017) 70-81.","DOI":"10.1016\/j.jcss.2016.11.008"},{"key":"e_1_3_3_1_13_2","doi-asserted-by":"crossref","unstructured":"X. Deng T. Kameda and C. H. Papadimitriou How to learn an unknown environment I: the rectilinear case Journal of the ACM 45 (1998) 215-245.","DOI":"10.1145\/274787.274788"},{"key":"e_1_3_3_1_14_2","doi-asserted-by":"crossref","unstructured":"A.K. Dhar B. Gorain K. Mondal S. Patra R.R. Singh Edge exploration of a graph by mobile agent Proc. 13th International Conference on Combinatorial Optimization and Applications (COCOA 2019) 142-154.","DOI":"10.1007\/978-3-030-36412-0_12"},{"key":"e_1_3_3_1_15_2","doi-asserted-by":"crossref","unstructured":"K. Diks P. Fraigniaud E. Kranakis and A. Pelc Tree exploration with little memory Journal of Algorithms 51 (2004) 38-63.","DOI":"10.1016\/j.jalgor.2003.10.002"},{"key":"e_1_3_3_1_16_2","doi-asserted-by":"crossref","unstructured":"S. Dobrev R. Kralovic and E. Markou Online graph exploration with advice Proc. 19th International Colloquium on Structural Information and Communication Complexity (SIROCCO 2012) 267-278.","DOI":"10.1007\/978-3-642-31104-8_23"},{"key":"e_1_3_3_1_17_2","doi-asserted-by":"crossref","unstructured":"Christian A. Duncan Stephen G. Kobourov V. S. Anil Kumar: Optimal constrained graph exploration. ACM Trans. Algorithms 2 (2006) 380-402.","DOI":"10.1145\/1159892.1159897"},{"key":"e_1_3_3_1_18_2","doi-asserted-by":"crossref","unstructured":"P. Fraigniaud D. Ilcinkas A. Pelc. Tree exploration with advice Information and Computation 206 (2008) 1276\u20131287.","DOI":"10.1016\/j.ic.2008.07.005"},{"key":"e_1_3_3_1_19_2","doi-asserted-by":"crossref","unstructured":"Roberto Baldoni Fran\u00e7ois Bonnet Alessia Milani Michel Raynal. Anonymous graph exploration without collision by mobile robots. Inf. Process. Lett. 109(2) (2008): 98-103.","DOI":"10.1016\/j.ipl.2008.08.011"},{"key":"e_1_3_3_1_20_2","doi-asserted-by":"crossref","unstructured":"P. Fraigniaud and D. Ilcinkas. Directed graphs exploration with little memory Proc. 21st Symposium on Theoretical Aspects of Computer Science (STACS 2004) 246-257.","DOI":"10.1007\/978-3-540-24749-4_22"},{"key":"e_1_3_3_1_21_2","doi-asserted-by":"crossref","unstructured":"X. Gong B. Wang S. Liang Collision-free cooperative motion planning and decision making for connected and automated vehicles at unsignalized intersections IEEE Trans. on Systems Man and Cybernetics : Systems 54 (2024) 2744-2756.","DOI":"10.1109\/TSMC.2023.3346275"},{"key":"e_1_3_3_1_22_2","doi-asserted-by":"crossref","unstructured":"B. Gorain A. Pelc Deterministic graph exploration with advice. ACM Trans. Algorithms 15 (2019) 8:1-8:17.","DOI":"10.1145\/3280823"},{"key":"e_1_3_3_1_23_2","doi-asserted-by":"crossref","unstructured":"M. Kouck\u00fd Universal traversal sequences with backtracking Journal of Computer and System Sciences 65 (2002) 717-726.","DOI":"10.1016\/S0022-0000(02)00023-5"},{"key":"e_1_3_3_1_24_2","unstructured":"Y. Nakaminami T. Masuzawa T. Herman Self-stabilizing agent traversal on tree networks IEICE Trans. 87-D (12) (20034) 2773-2780."},{"key":"e_1_3_3_1_25_2","doi-asserted-by":"crossref","unstructured":"P. Panaite and A. Pelc Exploring unknown undirected graphs Journal of Algorithms 33 (1999) 281-295.","DOI":"10.1006\/jagm.1999.1043"},{"key":"e_1_3_3_1_26_2","doi-asserted-by":"crossref","unstructured":"A. Pelc A. Tiane Efficient grid exploration with a stationary token International Journal of Foundations of Computer Science 25 (2014) 247-262.","DOI":"10.1142\/S0129054114500129"},{"key":"e_1_3_3_1_27_2","unstructured":"N. S. V. Rao S. Kareti W. Shi and S.S. Iyengar Robot navigation in unknown terrains: Introductory survey of non-heuristic algorithms Tech. Report ORNL\/TM-12410 Oak Ridge National Laboratory July 1993."},{"key":"e_1_3_3_1_28_2","doi-asserted-by":"crossref","unstructured":"O. Reingold Undirected connectivity in log-space Journal of the ACM 55 (2008) 17:1-17:24.","DOI":"10.1145\/1391289.1391291"},{"key":"e_1_3_3_1_29_2","doi-asserted-by":"crossref","unstructured":"Y. Wen P. Pagilla Path-constrained and collision-free optimal trajectory planning for robot manipulators IEEE Trans. on Automaton Science and Engineering 20 (2023) 763-744.","DOI":"10.1109\/TASE.2022.3169989"}],"event":{"name":"ICDCN 2025: 26th International Conference on Distributed Computing and Networking","location":"Hyderabad India","acronym":"ICDCN 2025"},"container-title":["Proceedings of the 26th International Conference on Distributed Computing and Networking"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3700838.3700858","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3700838.3700858","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T01:10:22Z","timestamp":1750295422000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3700838.3700858"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,1,4]]},"references-count":28,"alternative-id":["10.1145\/3700838.3700858","10.1145\/3700838"],"URL":"https:\/\/doi.org\/10.1145\/3700838.3700858","relation":{},"subject":[],"published":{"date-parts":[[2025,1,4]]},"assertion":[{"value":"2025-01-04","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}