{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T08:05:06Z","timestamp":1742976306997,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":29,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642220111"},{"type":"electronic","value":"9783642220128"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011]]},"DOI":"10.1007\/978-3-642-22012-8_38","type":"book-chapter","created":{"date-parts":[[2011,6,18]],"date-time":"2011-06-18T07:29:39Z","timestamp":1308382179000},"page":"478-489","source":"Crossref","is-referenced-by-count":10,"title":["Online Graph Exploration: New Results on Old and New Algorithms"],"prefix":"10.1007","author":[{"given":"Nicole","family":"Megow","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kurt","family":"Mehlhorn","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pascal","family":"Schweitzer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"4","key":"38_CR1","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.\u00a029(4), 1164\u20131188 (2000)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"38_CR2","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1016\/j.ipl.2009.10.013","volume":"110","author":"Y. Asahiro","year":"2010","unstructured":"Asahiro, Y., Miyano, E., Miyazaki, S., Yoshimuta, T.: Weighted nearest neighbor algorithms for the graph exploration problem on cycles. Inf. Process. Lett.\u00a0110(3), 93\u201398 (2010)","journal-title":"Inf. Process. Lett."},{"issue":"4","key":"38_CR3","doi-asserted-by":"publisher","first-page":"560","DOI":"10.1007\/s004530010071","volume":"29","author":"G. Ausiello","year":"2001","unstructured":"Ausiello, G., Feuerstein, E., Leonardi, S., Stougie, L., Talamo, M.: Algorithms for the on-line travelling salesman. Algorithmica\u00a029(4), 560\u2013581 (2001)","journal-title":"Algorithmica"},{"issue":"2","key":"38_CR4","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.\u00a0152(2), 155\u2013172 (1999)","journal-title":"Inf. Comput."},{"issue":"2","key":"38_CR5","doi-asserted-by":"publisher","first-page":"234","DOI":"10.1006\/inco.1993.1054","volume":"106","author":"R.A. Baeza-Yates","year":"1993","unstructured":"Baeza-Yates, R.A., Culberson, J.C., Rawlins, G.J.E.: Searching in the plane. Information and Computation\u00a0106(2), 234\u2013252 (1993)","journal-title":"Information and Computation"},{"key":"38_CR6","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 FOCS, pp. 75\u201385 (1994)","DOI":"10.1109\/SFCS.1994.365703"},{"key":"38_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"232","DOI":"10.1007\/BFb0029571","volume-title":"Online Algorithms: The State of the Art","author":"P. Berman","year":"1998","unstructured":"Berman, P.: On-line searching and navigation. In: Fiat, A. (ed.) Dagstuhl Seminar 1996. LNCS, vol.\u00a01442, pp. 232\u2013241. Springer, Heidelberg (1998)"},{"key":"38_CR8","first-page":"231","volume":"18","author":"M. Betke","year":"1995","unstructured":"Betke, M., Rivest, R.L., Singh, M.: Piecemeal learning of an unknown environment. Machine Learning\u00a018, 231\u2013254 (1995)","journal-title":"Machine Learning"},{"key":"38_CR9","volume-title":"Online Computation and Competitive Analysis","author":"A. Borodin","year":"1998","unstructured":"Borodin, A., El-Yaniv, R.: Online Computation and Competitive Analysis. Cambridge University Press, Cambridge (1998)"},{"key":"38_CR10","doi-asserted-by":"crossref","unstructured":"Deng, X., Papadimitriou, C.H.: Exploring an unknown graph (extended abstract). In: Proceedings of FOCS, pp. 355\u2013361 (1990)","DOI":"10.1109\/FSCS.1990.89554"},{"issue":"1-3","key":"38_CR11","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1016\/j.tcs.2004.07.031","volume":"326","author":"A. Dessmark","year":"2004","unstructured":"Dessmark, A., Pelc, A.: Optimal graph exploration without good maps. Theoretical Computer Science\u00a0326(1-3), 343\u2013362 (2004)","journal-title":"Theoretical Computer Science"},{"key":"38_CR12","doi-asserted-by":"publisher","first-page":"380","DOI":"10.1145\/1159892.1159897","volume":"2","author":"C.A. Duncan","year":"2006","unstructured":"Duncan, C.A., Kobourov, S.G., Kumar, V.S.A.: Optimal constrained graph exploration. ACM Trans. Algorithms\u00a02, 380\u2013402 (2006)","journal-title":"ACM Trans. Algorithms"},{"key":"38_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"327","DOI":"10.1007\/11821069_29","volume-title":"Mathematical Foundations of Computer Science 2006","author":"M. Dynia","year":"2006","unstructured":"Dynia, M., Kuty\u0142owski, J., der Heide, F.M.a., Schindelhauer, C.: Smart robot teams exploring sparse trees. In: Kr\u00e1lovi\u010d, R., Urzyczyn, P. (eds.) MFCS 2006. LNCS, vol.\u00a04162, pp. 327\u2013338. Springer, Heidelberg (2006)"},{"key":"38_CR14","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., Lopuszanski, J., Schindelhauer, C.: Why robots need maps. In: Prencipe, G., Zaks, S. (eds.) SIROCCO 2007. LNCS, vol.\u00a04474, pp. 41\u201350. Springer, Heidelberg (2007)"},{"key":"38_CR15","doi-asserted-by":"publisher","first-page":"34","DOI":"10.4153\/CJM-1959-003-9","volume":"11","author":"P. Erd\u0151s","year":"1959","unstructured":"Erd\u0151s, P.: Graph theory and probability. Canad. J. Math.\u00a011, 34\u201338 (1959)","journal-title":"Canad. J. Math."},{"key":"38_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1007\/11561071_4","volume-title":"Algorithms \u2013 ESA 2005","author":"R. Fleischer","year":"2005","unstructured":"Fleischer, R., Trippen, G.: Exploring an unknown graph efficiently. In: Brodal, G.S., Leonardi, S. (eds.) ESA 2005. LNCS, vol.\u00a03669, pp. 11\u201322. Springer, Heidelberg (2005)"},{"key":"38_CR17","doi-asserted-by":"publisher","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. Netw.\u00a048, 166\u2013177 (2006)","journal-title":"Netw."},{"issue":"12","key":"38_CR18","doi-asserted-by":"publisher","first-page":"2310","DOI":"10.1016\/j.dam.2007.11.001","volume":"156","author":"P. Fraigniaud","year":"2008","unstructured":"Fraigniaud, P., Ilcinkas, D., Pelc, A.: Impact of memory size on graph exploration capability. Discrete Applied Mathematics\u00a0156(12), 2310\u20132319 (2008)","journal-title":"Discrete Applied Mathematics"},{"key":"38_CR19","volume-title":"Search Games","author":"S. Gal","year":"1980","unstructured":"Gal, S.: Search Games. Academic Press, London (1980)"},{"key":"38_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"14","DOI":"10.1007\/978-3-540-92248-3_2","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"L. G\u0105sieniec","year":"2008","unstructured":"G\u0105sieniec, L., Radzik, T.: Memory efficient anonymous graph exploration. In: Broersma, H., Erlebach, T., Friedetzky, T., Paulusma, D. (eds.) WG 2008. LNCS, vol.\u00a05344, pp. 14\u201329. Springer, Heidelberg (2008)"},{"key":"38_CR21","volume-title":"The Traveling Salesman Problem and Its Variations","author":"G. Gutin","year":"2002","unstructured":"Gutin, G., Punnen, A.P.: The Traveling Salesman Problem and Its Variations. Springer, Heidelberg (2002)"},{"issue":"1","key":"38_CR22","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0167-6377(03)00093-2","volume":"32","author":"C.A.J. Hurkens","year":"2004","unstructured":"Hurkens, C.A.J., Woeginger, G.J.: On the nearest neighbor rule for the traveling salesman problem. Operations Research Letters\u00a032(1), 1\u20134 (2004)","journal-title":"Operations Research Letters"},{"issue":"1","key":"38_CR23","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1016\/0304-3975(94)90155-4","volume":"130","author":"B. Kalyanasundaram","year":"1994","unstructured":"Kalyanasundaram, B., Pruhs, K.: Constructing competitive tours from local information. Theor. Comput. Sci.\u00a0130(1), 125\u2013138 (1994)","journal-title":"Theor. Comput. Sci."},{"key":"38_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1007\/3-540-63307-3_73","volume-title":"Algorithms and Data Structures","author":"S. Kwek","year":"1997","unstructured":"Kwek, S.: On a simple depth-first search strategy for exploring unknown graphs. In: Rau-Chaplin, A., Dehne, F., Sack, J.-R., Tamassia, R. (eds.) WADS 1997. LNCS, vol.\u00a01272, pp. 345\u2013353. Springer, Heidelberg (1997)"},{"issue":"9","key":"38_CR25","doi-asserted-by":"publisher","first-page":"1620","DOI":"10.1587\/transinf.E92.D.1620","volume":"E92.D","author":"S. Miyazaki","year":"2009","unstructured":"Miyazaki, S., Morimoto, N., Okabe, Y.: The online graph exploration problem on restricted graphs. IEICE Transactions on Information and Systems\u00a0E92.D(9), 1620\u20131627 (2009)","journal-title":"IEICE Transactions on Information and Systems"},{"issue":"2","key":"38_CR26","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. Journal of Algorithms\u00a033(2), 281\u2013295 (1999)","journal-title":"Journal of Algorithms"},{"issue":"1","key":"38_CR27","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1016\/0304-3975(91)90263-2","volume":"84","author":"C. Papadimitriou","year":"1991","unstructured":"Papadimitriou, C., Yannakakis, M.: Shortest paths without a map. Theoretical Computer Science\u00a084(1), 127\u2013150 (1991)","journal-title":"Theoretical Computer Science"},{"key":"38_CR28","doi-asserted-by":"crossref","unstructured":"Rao, N., Kareti, S., Shi, W., Iyengar, S.: Robot navigation in unknown terrains: Introductory survey of nonheuristic algorithms. Report ORNL\/TM-12410, Oak Ridge Nat. Lab (1993)","DOI":"10.2172\/10180101"},{"issue":"3","key":"38_CR29","doi-asserted-by":"publisher","first-page":"563","DOI":"10.1137\/0206041","volume":"6","author":"D.J. Rosenkrantz","year":"1977","unstructured":"Rosenkrantz, D.J., Stearns, R.E., Lewis II, P.M.: An analysis of several heuristics for the traveling salesman problem. SIAM J. Comput.\u00a06(3), 563\u2013581 (1977)","journal-title":"SIAM J. Comput."}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-22012-8_38","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,6]],"date-time":"2025-03-06T09:46:19Z","timestamp":1741254379000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-22012-8_38"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642220111","9783642220128"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-22012-8_38","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}