{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T04:18:57Z","timestamp":1743049137245,"version":"3.40.3"},"publisher-location":"Cham","reference-count":21,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031215339"},{"type":"electronic","value":"9783031215346"}],"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:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,1,18]],"date-time":"2023-01-18T00:00:00Z","timestamp":1674000000000},"content-version":"vor","delay-in-days":382,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2022]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We review the space complexity of deterministically exploring undirected graphs. We assume that vertices are indistinguishable and that edges have a locally unique color that guides the traversal of a space-constrained agent. The graph is considered to be explored once the agent has visited all vertices. We visit results for this setting showing that <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\varTheta \\,(\\log n)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>\u0398<\/mml:mi>\n                    <mml:mspace\/>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mo>log<\/mml:mo>\n                    <mml:mi>n<\/mml:mi>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> bits of memory are necessary and sufficient for an agent to explore all <jats:italic>n<\/jats:italic>-vertex graphs. We then illustrate that, if agents only have sublogarithmic memory, the number of (distinguishable) agents needed for collaborative exploration is\u00a0<jats:inline-formula><jats:alternatives><jats:tex-math>$$\\varTheta \\,(\\log \\log n)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>\u0398<\/mml:mi>\n                    <mml:mspace\/>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mo>log<\/mml:mo>\n                    <mml:mo>log<\/mml:mo>\n                    <mml:mi>n<\/mml:mi>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>.<\/jats:p>","DOI":"10.1007\/978-3-031-21534-6_8","type":"book-chapter","created":{"date-parts":[[2023,1,17]],"date-time":"2023-01-17T20:02:53Z","timestamp":1673985773000},"page":"152-166","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["The Space Complexity of \u00a0Undirected Graph Exploration"],"prefix":"10.1007","author":[{"given":"Yann","family":"Disser","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Max","family":"Klimm","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,1,18]]},"reference":[{"key":"8_CR1","doi-asserted-by":"publisher","unstructured":"Aleliunas, R., Karp, R.M., Lipton, R.J., Lov\u00e1sz, L., Rackoff, C.: Random walks, universal traversal sequences, and the complexity of maze problems. In: FOCS, pp. 218\u2013223. IEEE Computer Society (1979). https:\/\/doi.org\/10.1109\/SFCS.1979.34","DOI":"10.1109\/SFCS.1979.34"},{"issue":"2","key":"8_CR2","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1007\/BF02579166","volume":"6","author":"N Alon","year":"1986","unstructured":"Alon, N.: Eigenvalues and expanders. Combinatorica 6(2), 83\u201396 (1986). https:\/\/doi.org\/10.1007\/BF02579166","journal-title":"Combinatorica"},{"key":"8_CR3","doi-asserted-by":"publisher","unstructured":"Alon, N., Milman, V.D.: $$\\lambda _1$$, isoperimetric inequalities for graphs, and superconcentrators. J. Comb. Theory, Ser. B 38(1), 73\u201388 (1985). https:\/\/doi.org\/10.1016\/0095-8956(85)90092-9","DOI":"10.1016\/0095-8956(85)90092-9"},{"issue":"2","key":"8_CR4","doi-asserted-by":"publisher","first-page":"271","DOI":"10.1002\/rsa.3240050203","volume":"5","author":"N Alon","year":"1994","unstructured":"Alon, N., Roichman, Y.: Random Cayley graphs and expanders. Random Struct. Algorithms 5(2), 271\u2013285 (1994). https:\/\/doi.org\/10.1002\/rsa.3240050203","journal-title":"Random Struct. Algorithms"},{"issue":"1","key":"8_CR5","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1017\/S0963548399004071","volume":"9","author":"N Alon","year":"2000","unstructured":"Alon, N., Sudakov, B.: Bipartite subgraphs and the smallest eigenvalue. Comb. Probab. Comput. 9(1), 1\u201312 (2000). https:\/\/doi.org\/10.1017\/S0963548399004071","journal-title":"Comb. Probab. Comput."},{"key":"8_CR6","doi-asserted-by":"publisher","unstructured":"Blum, M., Kozen, D.: On the power of the compass (or, why mazes are easier to search than graphs). In: FOCS, pp. 132\u2013142. IEEE Computer Society (1978). https:\/\/doi.org\/10.1109\/SFCS.1978.30","DOI":"10.1109\/SFCS.1978.30"},{"key":"8_CR7","doi-asserted-by":"publisher","unstructured":"Blum, M., Sakoda, W.J.: On the capability of finite automata in 2 and 3 dimensional space. In: FOCS, pp. 147\u2013161. IEEE Computer Society (1977). https:\/\/doi.org\/10.1109\/SFCS.1977.20","DOI":"10.1109\/SFCS.1977.20"},{"key":"8_CR8","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1002\/mana.19780860120","volume":"86","author":"L Budach","year":"1978","unstructured":"Budach, L.: Automata and labyrinths. Math. Nachrichten 86, 195\u2013282 (1978). https:\/\/doi.org\/10.1002\/mana.19780860120","journal-title":"Math. Nachrichten"},{"key":"8_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1007\/978-3-642-17653-1_10","volume-title":"Principles of Distributed Systems","author":"J Chalopin","year":"2010","unstructured":"Chalopin, J., Das, S., Kosowski, A.: Constructing a map of an anonymous graph: applications of universal sequences. In: Lu, C., Masuzawa, T., Mosbah, M. (eds.) OPODIS 2010. LNCS, vol. 6490, pp. 119\u2013134. Springer, Heidelberg (2010). https:\/\/doi.org\/10.1007\/978-3-642-17653-1_10"},{"key":"8_CR10","doi-asserted-by":"publisher","unstructured":"Disser, Y., Hackfeld, J., Klimm, M.: Tight bounds for undirected graph exploration with pebbles and multiple agents. J. ACM 66(6), 40:1\u201340:41 (2019). https:\/\/doi.org\/10.1145\/3356883","DOI":"10.1145\/3356883"},{"issue":"6","key":"8_CR11","doi-asserted-by":"publisher","first-page":"859","DOI":"10.1109\/70.105395","volume":"7","author":"G Dudek","year":"1991","unstructured":"Dudek, G., Jenkin, M., Milios, E.E., Wilkes, D.: Robotic exploration as graph construction. IEEE Trans. Robot. Autom. 7(6), 859\u2013865 (1991). https:\/\/doi.org\/10.1109\/70.105395","journal-title":"IEEE Trans. Robot. Autom."},{"issue":"2\u20133","key":"8_CR12","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). https:\/\/doi.org\/10.1016\/j.tcs.2005.07.014","journal-title":"Theor. Comput. Sci."},{"key":"8_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/11685654_1","volume-title":"Theoretical Computer Science","author":"P Fraigniaud","year":"2006","unstructured":"Fraigniaud, P., Ilcinkas, D., Rajsbaum, S., Tixeuil, S.: The reduced automata technique for graph exploration space lower bounds. In: Goldreich, O., Rosenberg, A.L., Selman, A.L. (eds.) Theoretical Computer Science. LNCS, vol. 3895, pp. 1\u201326. Springer, Heidelberg (2006). https:\/\/doi.org\/10.1007\/11685654_1"},{"key":"8_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"433","DOI":"10.1007\/3-540-10854-8_47","volume-title":"Fundamentals of Computation Theory","author":"F Hoffmann","year":"1981","unstructured":"Hoffmann, F.: One pebble does not suffice to search plane labyrinths. In: G\u00e9cseg, F. (ed.) FCT 1981. LNCS, vol. 117, pp. 433\u2013444. Springer, Heidelberg (1981). https:\/\/doi.org\/10.1007\/3-540-10854-8_47"},{"issue":"4","key":"8_CR15","doi-asserted-by":"publisher","first-page":"717","DOI":"10.1016\/S0022-0000(02)00023-5","volume":"65","author":"M Kouck\u00fd","year":"2002","unstructured":"Kouck\u00fd, M.: Universal traversal sequences with backtracking. J. Comput. Syst. Sci. 65(4), 717\u2013726 (2002). https:\/\/doi.org\/10.1016\/S0022-0000(02)00023-5","journal-title":"J. Comput. Syst. Sci."},{"key":"8_CR16","doi-asserted-by":"publisher","unstructured":"Reingold, O.: Undirected connectivity in log-space. J. ACM 55(4), 17:1\u201317:24 (2008). https:\/\/doi.org\/10.1145\/1391289.1391291","DOI":"10.1145\/1391289.1391291"},{"issue":"1","key":"8_CR17","doi-asserted-by":"publisher","first-page":"157","DOI":"10.2307\/3062153","volume":"155","author":"O Reingold","year":"2002","unstructured":"Reingold, O., Vadhan, S., Wigderson, A.: Entropy waves, the zig-zag graph product, and new constant-degree expanders. Ann. Math. 155(1), 157\u2013187 (2002). https:\/\/doi.org\/10.2307\/3062153","journal-title":"Ann. Math."},{"key":"8_CR18","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1007\/BF00288647","volume":"13","author":"H Rollik","year":"1980","unstructured":"Rollik, H.: Automaten in planaren graphen. Acta Informatica 13, 287\u2013298 (1980). https:\/\/doi.org\/10.1007\/BF00288647","journal-title":"Acta Informatica"},{"key":"8_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"436","DOI":"10.1007\/11538462_37","volume-title":"Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques","author":"E Rozenman","year":"2005","unstructured":"Rozenman, E., Vadhan, S.: Derandomized squaring of graphs. In: Chekuri, C., Jansen, K., Rolim, J.D.P., Trevisan, L. (eds.) APPROX\/RANDOM -2005. LNCS, vol. 3624, pp. 436\u2013447. Springer, Heidelberg (2005). https:\/\/doi.org\/10.1007\/11538462_37"},{"issue":"3","key":"8_CR20","doi-asserted-by":"publisher","first-page":"236","DOI":"10.1016\/0146-664X(74)90017-3","volume":"3","author":"AN Shah","year":"1974","unstructured":"Shah, A.N.: Pebble automata on arrays. Comput. Graph. Image Process. 3(3), 236\u2013246 (1974). https:\/\/doi.org\/10.1016\/0146-664X(74)90017-3","journal-title":"Comput. Graph. Image Process."},{"issue":"3","key":"8_CR21","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1137\/0605030","volume":"5","author":"RM Tanner","year":"1984","unstructured":"Tanner, R.M.: Explicit concentrators from generalized $$n$$-gons. SIAM J. Alg. Disc. Meth. 5(3), 287\u2013293 (1984). https:\/\/doi.org\/10.1137\/0605030","journal-title":"SIAM J. Alg. Disc. Meth."}],"container-title":["Lecture Notes in Computer Science","Algorithms for Big Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-21534-6_8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,17]],"date-time":"2023-01-17T20:03:33Z","timestamp":1673985813000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-21534-6_8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022]]},"ISBN":["9783031215339","9783031215346"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-21534-6_8","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":"18 January 2023","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}