{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,28]],"date-time":"2026-04-28T05:44:46Z","timestamp":1777355086531,"version":"3.51.4"},"reference-count":21,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2026,2,28]],"date-time":"2026-02-28T00:00:00Z","timestamp":1772236800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2026,2,28]],"date-time":"2026-02-28T00:00:00Z","timestamp":1772236800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["ANR-22-CE25-0008-01"],"award-info":[{"award-number":["ANR-22-CE25-0008-01"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2026,4]]},"DOI":"10.1007\/s00453-026-01378-4","type":"journal-article","created":{"date-parts":[[2026,2,28]],"date-time":"2026-02-28T11:12:47Z","timestamp":1772277167000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Graph Exploration: The Impact of a Distance Constraint"],"prefix":"10.1007","volume":"88","author":[{"given":"St\u00e9phane","family":"Devismes","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yoann","family":"Dieudonn\u00e9","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Arnaud","family":"Labourel","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2026,2,28]]},"reference":[{"issue":"3","key":"1378_CR1","doi-asserted-by":"publisher","first-page":"380","DOI":"10.1145\/1159892.1159897","volume":"2","author":"CA Duncan","year":"2006","unstructured":"Duncan, C.A., Kobourov, S.G., Kumar, V.S.A.: Optimal constrained graph exploration. ACM Trans. Algorithms 2(3), 380\u2013402 (2006). https:\/\/doi.org\/10.1145\/1159892.1159897","journal-title":"ACM Trans. Algorithms"},{"issue":"2","key":"1378_CR2","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1006\/JAGM.1999.1043","volume":"33","author":"P Panaite","year":"1999","unstructured":"Panaite, P., Pelc, A.: Exploring unknown undirected graphs. J. Algorithms 33(2), 281\u2013295 (1999). https:\/\/doi.org\/10.1006\/JAGM.1999.1043","journal-title":"J. Algorithms"},{"issue":"2\u20133","key":"1378_CR3","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1007\/BF00993411","volume":"18","author":"M Betke","year":"1995","unstructured":"Betke, M., Rivest, R.L., Singh, M.: Piecemeal learning of an unknown environment. Mach. Learn. 18(2\u20133), 231\u2013254 (1995). https:\/\/doi.org\/10.1007\/BF00993411","journal-title":"Mach. Learn."},{"key":"1378_CR4","doi-asserted-by":"publisher","unstructured":"Das, S.: Graph explorations with mobile agents. In: Flocchini, P., Prencipe, G., Santoro, N. (eds.) Distributed Computing by Mobile Entities, Current Research in Moving and Computing. Lecture Notes in Computer Science, vol. 11340, pp. 403\u2013422 (2019) https:\/\/doi.org\/10.1007\/978-3-030-11072-7_16","DOI":"10.1007\/978-3-030-11072-7_16"},{"key":"1378_CR5","unstructured":"Shannon, C.E.: Presentation of a maze-solving machine. In: 8th Conference of the Josiah Macy Jr. Found. (Cybernetics), pp. 173\u2013180 (1951)"},{"issue":"10\u201312","key":"1378_CR6","first-page":"661","volume":"11","author":"L Budach","year":"1975","unstructured":"Budach, L.: On the solution of the labyrinth problem for finite automata. J. Inf. Process. Cybern. 11(10\u201312), 661\u2013672 (1975)","journal-title":"J. Inf. Process. Cybern."},{"key":"1378_CR7","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: 19th Annual Symposium on Foundations of Computer Science, Ann Arbor, Michigan, USA, 16\u201318 October 1978, pp. 132\u2013142 (1978) https:\/\/doi.org\/10.1109\/SFCS.1978.30","DOI":"10.1109\/SFCS.1978.30"},{"key":"1378_CR8","doi-asserted-by":"publisher","unstructured":"Hoffmann, F.: One pebble does not suffice to search plane labyrinths. In: G\u00e9cseg, F. (ed.) Fundamentals of Computation Theory, FCT\u201981, Proceedings of the 1981 International FCT-Conference, Szeged, Hungary, August 24\u201328, 1981. Lecture Notes in Computer Science, vol. 117, pp. 433\u2013444 (1981). https:\/\/doi.org\/10.1007\/3-540-10854-8_47","DOI":"10.1007\/3-540-10854-8_47"},{"issue":"1","key":"1378_CR9","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1006\/INCO.2001.3081","volume":"176","author":"MA Bender","year":"2002","unstructured":"Bender, M.A., Fern\u00e1ndez, A., Ron, D., Sahai, A., Vadhan, S.P.: The power of a pebble: Exploring and mapping directed graphs. Inf. Comput. 176(1), 1\u201321 (2002). https:\/\/doi.org\/10.1006\/INCO.2001.3081","journal-title":"Inf. Comput."},{"key":"1378_CR10","doi-asserted-by":"publisher","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.) Principles of Distributed Systems - 14th International Conference, OPODIS 2010, Tozeur, Tunisia, December 14\u201317, 2010. Proceedings. Lecture Notes in Computer Science, vol. 6490, pp. 119\u2013134 (2010). https:\/\/doi.org\/10.1007\/978-3-642-17653-1_10","DOI":"10.1007\/978-3-642-17653-1_10"},{"issue":"12","key":"1378_CR11","doi-asserted-by":"publisher","first-page":"467","DOI":"10.1016\/J.IPL.2012.03.017","volume":"112","author":"Y Dieudonn\u00e9","year":"2012","unstructured":"Dieudonn\u00e9, Y., Pelc, A.: Deterministic network exploration by a single agent with byzantine tokens. Inf. Process. Lett. 112(12), 467\u2013470 (2012). https:\/\/doi.org\/10.1016\/J.IPL.2012.03.017","journal-title":"Inf. Process. Lett."},{"issue":"6","key":"1378_CR12","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. Robotics Autom. 7(6), 859\u2013865 (1991). https:\/\/doi.org\/10.1109\/70.105395","journal-title":"IEEE Trans. Robotics Autom."},{"key":"1378_CR13","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: 20th Annual Symposium on Foundations of Computer Science, San Juan, Puerto Rico, 29\u201331 October 1979, pp. 218\u2013223 (1979) https:\/\/doi.org\/10.1109\/SFCS.1979.34","DOI":"10.1109\/SFCS.1979.34"},{"key":"1378_CR14","doi-asserted-by":"publisher","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. Special Issue on Complexity 2001","DOI":"10.1016\/S0022-0000(02)00023-5"},{"issue":"4","key":"1378_CR15","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1145\/1391289.1391291","volume":"55","author":"O Reingold","year":"2008","unstructured":"Reingold, O.: Undirected connectivity in log-space. J. ACM 55(4), 17\u201311724 (2008). https:\/\/doi.org\/10.1145\/1391289.1391291","journal-title":"J. ACM"},{"issue":"2\u20133","key":"1378_CR16","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."},{"issue":"4","key":"1378_CR17","doi-asserted-by":"publisher","first-page":"1164","DOI":"10.1137\/S009753979732428X","volume":"29","author":"S Albers","year":"2000","unstructured":"Albers, S., Henzinger, M.R.: Exploring unknown environments. SIAM J. Comput. 29(4), 1164\u20131188 (2000). https:\/\/doi.org\/10.1137\/S009753979732428X","journal-title":"SIAM J. Comput."},{"issue":"2","key":"1378_CR18","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1006\/inco.1999.2795","volume":"152","author":"B Awerbuch","year":"1999","unstructured":"Awerbuch, B., Betke, M., Rivest, R.L., Singh, M.: Piecemeal graph exploration by a mobile robot. Inf. Comput. 152(2), 155\u2013172 (1999). https:\/\/doi.org\/10.1006\/inco.1999.2795","journal-title":"Inf. Comput."},{"key":"1378_CR19","doi-asserted-by":"publisher","unstructured":"Awerbuch, B., Kobourov, S.G.: Polylogarithmic-overhead piecemeal graph exploration. In: Bartlett, P.L., Mansour, Y. (eds.) Proceedings of the Eleventh Annual Conference on Computational Learning Theory, COLT 1998, Madison, Wisconsin, USA, July 24\u201326, 1998, pp. 280\u2013286 (1998). https:\/\/doi.org\/10.1145\/279943.279998","DOI":"10.1145\/279943.279998"},{"issue":"3","key":"1378_CR20","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1002\/(SICI)1097-0118(199911)32:3<265::AID-JGT6>3.0.CO;2-8","volume":"32","author":"X Deng","year":"1999","unstructured":"Deng, X., Papadimitriou, C.H.: Exploring an unknown graph. J. Graph Theory 32(3), 265\u2013297 (1999)","journal-title":"J. Graph Theory"},{"issue":"4","key":"1378_CR21","doi-asserted-by":"publisher","first-page":"453","DOI":"10.1007\/BF01456961","volume":"77","author":"D K\u00f6nig","year":"1916","unstructured":"K\u00f6nig, D.: \u00dcber graphen und ihre anwendung auf determinantentheorie und mengenlehre. Math. Ann. 77(4), 453\u2013465 (1916)","journal-title":"Math. Ann."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-026-01378-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-026-01378-4","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-026-01378-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,28]],"date-time":"2026-04-28T05:01:52Z","timestamp":1777352512000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-026-01378-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,2,28]]},"references-count":21,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2026,4]]}},"alternative-id":["1378"],"URL":"https:\/\/doi.org\/10.1007\/s00453-026-01378-4","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,2,28]]},"assertion":[{"value":"18 July 2025","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 February 2026","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 February 2026","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"24"}}