{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,1]],"date-time":"2025-11-01T13:01:58Z","timestamp":1762002118615,"version":"build-2065373602"},"publisher-location":"Cham","reference-count":25,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319720494"},{"type":"electronic","value":"9783319720500"}],"license":[{"start":{"date-parts":[[2017,1,1]],"date-time":"2017-01-01T00:00:00Z","timestamp":1483228800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2017]]},"DOI":"10.1007\/978-3-319-72050-0_8","type":"book-chapter","created":{"date-parts":[[2017,12,29]],"date-time":"2017-12-29T16:57:13Z","timestamp":1514566633000},"page":"125-139","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["A General Lower Bound for Collaborative Tree Exploration"],"prefix":"10.1007","author":[{"given":"Yann","family":"Disser","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Frank","family":"Mousset","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andreas","family":"Noever","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nemanja","family":"\u0160kori\u0107","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Angelika","family":"Steger","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2017,12,30]]},"reference":[{"issue":"4","key":"8_CR1","doi-asserted-by":"crossref","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)","journal-title":"SIAM J. Comput."},{"doi-asserted-by":"crossref","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: Proceedings of the 20th Annual Symposium on Foundations of Computer Science (FOCS), pp. 218\u2013223 (1979)","key":"8_CR2","DOI":"10.1109\/SFCS.1979.34"},{"issue":"4","key":"8_CR3","doi-asserted-by":"crossref","first-page":"481","DOI":"10.1017\/S0963548311000125","volume":"20","author":"N Alon","year":"2011","unstructured":"Alon, N., Avin, C., Kouck\u00fd, M., Kozma, G., Lotker, Z., Tuttle, M.R.: Many random walks are faster than one. Comb. Probab. Comput. 20(4), 481\u2013502 (2011)","journal-title":"Comb. Probab. Comput."},{"issue":"2","key":"8_CR4","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1921659.1921663","volume":"7","author":"C Amb\u00fchl","year":"2011","unstructured":"Amb\u00fchl, C., G\u0105sieniec, L., Pelc, A., Radzik, T., Zhang, X.: Tree exploration with logarithmic memory. ACM Trans. Algorithms 7(2), 1\u201321 (2011)","journal-title":"ACM Trans. Algorithms"},{"issue":"2","key":"8_CR5","doi-asserted-by":"crossref","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)","journal-title":"Inf. Comput."},{"issue":"1","key":"8_CR6","doi-asserted-by":"crossref","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.: The power of a pebble: exploring and mapping directed graphs. Inf. Comput. 176(1), 1\u201321 (2002)","journal-title":"Inf. Comput."},{"doi-asserted-by":"crossref","unstructured":"Bender, M.A., Slonim, D.K.: The power of team exploration: two robots can learn unlabeled directed graphs. In: Proceedings of 35th Annual Symposium on Foundations of Computer Science (FOCS), pp. 75\u201385 (1994)","key":"8_CR7","DOI":"10.1109\/SFCS.1994.365703"},{"doi-asserted-by":"crossref","unstructured":"Blum, M., Kozen, D.: On the power of the compass (or, why mazes are easier to search than graphs). In: Proceedings of the 19th Annual Symposium on Foundations of Computer Science (FOCS), pp. 132\u2013142 (1978)","key":"8_CR8","DOI":"10.1109\/SFCS.1978.30"},{"issue":"1","key":"8_CR9","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1007\/s00453-011-9572-8","volume":"65","author":"J Chalopin","year":"2011","unstructured":"Chalopin, J., Das, S., Disser, Y., Mihal\u00e1k, M., Widmayer, P.: Mapping simple polygons: how robots benefit from looking back. Algorithmica 65(1), 43\u201359 (2011)","journal-title":"Algorithmica"},{"issue":"4","key":"8_CR10","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/2700223","volume":"11","author":"J Chalopin","year":"2015","unstructured":"Chalopin, J., Das, S., Disser, Y., Mihal\u00e1k, M., Widmayer, P.: Mapping simple polygons. ACM Trans. Algorithms 11(4), 1\u201316 (2015)","journal-title":"ACM Trans. Algorithms"},{"issue":"3","key":"8_CR11","doi-asserted-by":"crossref","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"},{"key":"8_CR12","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1016\/j.ic.2014.12.005","volume":"243","author":"D Dereniowski","year":"2015","unstructured":"Dereniowski, D., Disser, Y., Kosowski, A., Paj\u0105k, D., Uzna\u0144ski, P.: Fast collaborative graph exploration. Inf. Comput. 243, 37\u201349 (2015)","journal-title":"Inf. Comput."},{"issue":"1","key":"8_CR13","doi-asserted-by":"crossref","first-page":"38","DOI":"10.1016\/j.jalgor.2003.10.002","volume":"51","author":"K Diks","year":"2004","unstructured":"Diks, K., Fraigniaud, P., Kranakis, E., Pelc, A.: Tree exploration with little memory. J. Algorithms 51(1), 38\u201363 (2004)","journal-title":"J. Algorithms"},{"doi-asserted-by":"crossref","unstructured":"Disser, Y., Hackfeld, J., Klimm, M.: Undirected graph exploration with $$\\varTheta (\\log \\log n)$$ pebbles. In: Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 25\u201339 (2016)","key":"8_CR14","DOI":"10.1137\/1.9781611974331.ch3"},{"key":"8_CR15","doi-asserted-by":"crossref","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, 380\u2013402 (2006)","journal-title":"ACM Trans. Algorithms"},{"key":"8_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1007\/978-3-540-72951-8_5","volume-title":"Structural Information and Communication Complexity","author":"M Dynia","year":"2007","unstructured":"Dynia, M., \u0141opusza\u0144ski, J., Schindelhauer, C.: Why robots need maps. In: Prencipe, G., Zaks, S. (eds.) SIROCCO 2007. LNCS, vol. 4474, pp. 41\u201350. Springer, Heidelberg (2007). https:\/\/doi.org\/10.1007\/978-3-540-72951-8_5"},{"issue":"24","key":"8_CR17","doi-asserted-by":"crossref","first-page":"2623","DOI":"10.1016\/j.tcs.2010.08.010","volume":"412","author":"R Els\u00e4sser","year":"2011","unstructured":"Els\u00e4sser, R., Sauerwald, T.: Tight bounds for the cover time of multiple random walks. Theor. Comput. Sci. 412(24), 2623\u20132641 (2011)","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"8_CR18","doi-asserted-by":"crossref","first-page":"166","DOI":"10.1002\/net.20127","volume":"48","author":"P Fraigniaud","year":"2006","unstructured":"Fraigniaud, P., G\u0105sieniec, L., Kowalski, D.R., Pelc, A.: Collective tree exploration. Networks 48(3), 166\u2013177 (2006)","journal-title":"Networks"},{"issue":"2\u20133","key":"8_CR19","doi-asserted-by":"crossref","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)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"8_CR20","doi-asserted-by":"crossref","first-page":"480","DOI":"10.1007\/s10878-012-9571-y","volume":"28","author":"Y Higashikawa","year":"2012","unstructured":"Higashikawa, Y., Katoh, N., Langerman, S., Tanigawa, S.I.: Online graph exploration algorithms for cycles and trees by multiple searchers. J. Comb. Optim. 28(2), 480\u2013495 (2012)","journal-title":"J. Comb. Optim."},{"doi-asserted-by":"crossref","unstructured":"Hoffmann, F.: One pebble does not suffice to search plane labyrinths. In: Proceedings of the 3rd International Symposium on Fundamentals of Computation Theory (FCT), pp. 433\u2013444 (1981)","key":"8_CR21","DOI":"10.1007\/3-540-10854-8_47"},{"doi-asserted-by":"crossref","unstructured":"Ortolf, C., Schindelhauer, C.: Online multi-robot exploration of grid graphs with rectangular obstacles. In: Proceedings of the 24th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pp. 27\u201336 (2012)","key":"8_CR22","DOI":"10.1145\/2312005.2312010"},{"key":"8_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1007\/978-3-319-09620-9_26","volume-title":"Structural Information and Communication Complexity","author":"C Ortolf","year":"2014","unstructured":"Ortolf, C., Schindelhauer, C.: A recursive approach to multi-robot exploration of trees. In: Halld\u00f3rsson, M.M. (ed.) SIROCCO 2014. LNCS, vol. 8576, pp. 343\u2013354. Springer, Cham (2014). https:\/\/doi.org\/10.1007\/978-3-319-09620-9_26"},{"key":"8_CR24","doi-asserted-by":"crossref","first-page":"178","DOI":"10.1016\/j.tcs.2015.09.026","volume":"608","author":"C Ortolf","year":"2015","unstructured":"Ortolf, C., Schindelhauer, C.: Strategies for parallel unaware cleaners. Theor. Comput. Sci. 608, 178\u2013189 (2015)","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"8_CR25","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1391289.1391291","volume":"55","author":"O Reingold","year":"2008","unstructured":"Reingold, O.: Undirected connectivity in log-space. J. ACM 55(4), 1\u201324 (2008)","journal-title":"J. ACM"}],"container-title":["Lecture Notes in Computer Science","Structural Information and Communication Complexity"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-72050-0_8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,10,8]],"date-time":"2019-10-08T21:21:39Z","timestamp":1570569699000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-72050-0_8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017]]},"ISBN":["9783319720494","9783319720500"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-72050-0_8","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2017]]}}}