{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,29]],"date-time":"2026-05-29T17:04:08Z","timestamp":1780074248629,"version":"3.54.0"},"reference-count":37,"publisher":"Association for Computing Machinery (ACM)","issue":"6","license":[{"start":{"date-parts":[[2019,10,16]],"date-time":"2019-10-16T00:00:00Z","timestamp":1571184000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2019,12,31]]},"abstract":"<jats:p>\n            We study the problem of deterministically exploring an undirected and initially unknown graph with\n            <jats:italic>n<\/jats:italic>\n            vertices either by a single agent equipped with a set of pebbles or by a set of collaborating agents. The vertices of the graph are unlabeled and cannot be distinguished by the agents, but the edges incident to a vertex have locally distinct labels. The graph is explored when all vertices have been visited by at least one agent. In this setting, it is known that for a single agent without pebbles \u0398(log\n            <jats:italic>n<\/jats:italic>\n            ) bits of memory are necessary and sufficient to explore any graph with at most\n            <jats:italic>n<\/jats:italic>\n            vertices. We are interested in how the memory requirement decreases as the agent may mark vertices by dropping and retrieving distinguishable pebbles or when multiple agents jointly explore the graph. We give tight results for both questions showing that for a single agent with constant memory \u0398(log log\n            <jats:italic>n<\/jats:italic>\n            ) pebbles are necessary and sufficient for exploration. We further prove that using collaborating agents instead of pebbles does not help as \u0398(log log\n            <jats:italic>n<\/jats:italic>\n            ) agents with constant memory each are necessary and sufficient for exploration.\n          <\/jats:p>\n          <jats:p>\n            For the upper bounds, we devise an algorithm for a single agent with constant memory that explores any\n            <jats:italic>n<\/jats:italic>\n            -vertex graph using\n            <jats:italic>O<\/jats:italic>\n            (log log\n            <jats:italic>n<\/jats:italic>\n            ) pebbles, even when\n            <jats:italic>n<\/jats:italic>\n            is not known\n            <jats:italic>a priori<\/jats:italic>\n            . The algorithm terminates after polynomial time and returns to the starting vertex. We further show that the algorithm can be realized with additional constant-memory agents rather than pebbles, implying that\n            <jats:italic>O<\/jats:italic>\n            (log log\n            <jats:italic>n<\/jats:italic>\n            ) agents with constant memory can explore any\n            <jats:italic>n<\/jats:italic>\n            -vertex graph. For the lower bound, we show that the number of agents needed for exploring any graph with at most\n            <jats:italic>n<\/jats:italic>\n            vertices is already \u03a9(log log\n            <jats:italic>n<\/jats:italic>\n            ) when we allow each agent to have at most\n            <jats:italic>O<\/jats:italic>\n            ((log\n            <jats:italic>n<\/jats:italic>\n            )\n            <jats:sup>1<\/jats:sup>\n            -\u03b5) bits of memory for any \u03b5 &gt; 0. Our argument also implies that a single agent with sublogarithmic memory needs \u0398(log log\n            <jats:italic>n<\/jats:italic>\n            ) pebbles to explore any\n            <jats:italic>n<\/jats:italic>\n            -vertex graph.\n          <\/jats:p>","DOI":"10.1145\/3356883","type":"journal-article","created":{"date-parts":[[2019,10,16]],"date-time":"2019-10-16T18:55:35Z","timestamp":1571252135000},"page":"1-41","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":18,"title":["Tight Bounds for Undirected Graph Exploration with Pebbles and Multiple Agents"],"prefix":"10.1145","volume":"66","author":[{"given":"Yann","family":"Disser","sequence":"first","affiliation":[{"name":"TU Darmstadt, Darmstadt, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jan","family":"Hackfeld","sequence":"additional","affiliation":[{"name":"HU Berlin, Berlin, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9061-2267","authenticated-orcid":false,"given":"Max","family":"Klimm","sequence":"additional","affiliation":[{"name":"HU Berlin, Berlin, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2019,10,16]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/S009753979732428X"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1979.34"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1921659.1921663"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.2001.3081"},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of the 35th Annual IEEE Symposium on Foundations of Computer Science (FOCS\u201994)","author":"Michael","unstructured":"Michael A. Bender and Donna K. Slonim. 1994. The power of team exploration: Two robots can learn unlabeled directed graphs. In Proceedings of the 35th Annual IEEE Symposium on Foundations of Computer Science (FOCS\u201994). 75--85."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539791194931"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1978.30"},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the 18th Annual IEEE Symposium on Foundations of Computer Science (FOCS). 147--161","author":"Blum Manuel","unstructured":"Manuel Blum and William J. Sakoda. 1977. On the capability of finite automata in 2 and 3 dimensional space. In Proceedings of the 18th Annual IEEE Symposium on Foundations of Computer Science (FOCS). 147--161."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1002\/mana.19780860120"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-011-9572-8"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2700223"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-17653-1_10"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/0209048"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/274787.274788"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1097-0118(199911)32:3<265::AID-JGT6>3.0.CO;2-8"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2003.10.002"},{"key":"e_1_2_1_17_1","volume-title":"Proceedinbgs of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201915)","author":"Disser Yann","year":"2015","unstructured":"Yann Disser, Jan Hackfeld, and Max Klimm. 2015. Undirected graph exploration with &Theta; (log log n) pebbles. In Proceedinbgs of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201915). 25--39."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/70.105395"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/11561071_4"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2015.11.017"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-24749-4_22"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.07.014"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2007.11.001"},{"key":"e_1_2_1_24_1","series-title":"Lecture Notes in Computer Science","volume-title":"Theoretical Computer Science, O. Goldreich, A. L. Rosenberg, and A. L. Selman","author":"Fraigniaud Pierre","unstructured":"Pierre Fraigniaud, David Ilcinkas, Sergio Rajsbaum, and S\u00e9bastien Tixeuil. 2006. The reduced automata technique for graph exploration space lower bounds. In Theoretical Computer Science, O. Goldreich, A. L. Rosenberg, and A. L. Selman. Lecture Notes in Computer Science, Vol. 3895. Springer, Berlin, Heidelberg."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-10854-8_47"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/62212.62260"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(94)90155-4"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(02)00023-5"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2012.06.034"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1587\/transinf.E92.D.1620"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01305237"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1391289.1391291"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00288647"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1137\/0206041"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(73)80031-5"},{"key":"e_1_2_1_37_1","first-page":"236","article-title":"Pebble automata on arrays","volume":"3","author":"Shah Anupam N.","year":"1974","unstructured":"Anupam N. Shah. 1974. Pebble automata on arrays. Comput. Vision Graph. 3, 3 (1974), 236--246.","journal-title":"Comput. Vision Graph."},{"key":"e_1_2_1_38_1","volume-title":"Proceedings of the 8th Conference on Cybernetics. 173--180","author":"Shannon Claude A.","year":"1951","unstructured":"Claude A. Shannon. 1951. Presentation of a maze-solving machine. In Proceedings of the 8th Conference on Cybernetics. 173--180."}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3356883","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3356883","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:22:56Z","timestamp":1750202576000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3356883"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,10,16]]},"references-count":37,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2019,12,31]]}},"alternative-id":["10.1145\/3356883"],"URL":"https:\/\/doi.org\/10.1145\/3356883","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,10,16]]},"assertion":[{"value":"2018-04-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-07-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-10-16","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}