{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,19]],"date-time":"2025-09-19T08:47:37Z","timestamp":1758271657359},"publisher-location":"Berlin, Heidelberg","reference-count":37,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642354755"},{"type":"electronic","value":"9783642354762"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-35476-2_11","type":"book-chapter","created":{"date-parts":[[2012,12,13]],"date-time":"2012-12-13T15:48:14Z","timestamp":1355413694000},"page":"151-165","source":"Crossref","is-referenced-by-count":9,"title":["Directed Graph Exploration"],"prefix":"10.1007","author":[{"given":"Klaus-Tycho","family":"F\u00f6rster","sequence":"first","affiliation":[]},{"given":"Roger","family":"Wattenhofer","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"4","key":"11_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."},{"key":"11_CR2","doi-asserted-by":"crossref","first-page":"379","DOI":"10.1137\/1.9781611973075.32","volume-title":"Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010","author":"A. Asadpour","year":"2010","unstructured":"Asadpour, A., Goemans, M.X., Madry, A., Gharan, S.O., Saberi, A.: An O(log n\/log log n)-approximation Algorithm for the Asymmetric Traveling Salesman Problem. In: Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010, pp. 379\u2013389. Society for Industrial and Applied Mathematics, Philadelphia (2010)"},{"issue":"2","key":"11_CR3","doi-asserted-by":"publisher","first-page":"290","DOI":"10.1016\/j.jda.2007.03.002","volume":"6","author":"G. Ausiello","year":"2008","unstructured":"Ausiello, G., Bonifaci, V., Laura, L.: The on-line asymmetric traveling salesman problem. J. Discrete Algorithms\u00a06(2), 290\u2013298 (2008)","journal-title":"J. Discrete Algorithms"},{"issue":"2","key":"11_CR4","doi-asserted-by":"publisher","first-page":"98","DOI":"10.1016\/j.ipl.2008.08.011","volume":"109","author":"R. Baldoni","year":"2008","unstructured":"Baldoni, R., Bonnet, F., Milani, A., Raynal, M.: Anonymous graph exploration without collision by mobile robots. Inf. Process. Lett.\u00a0109(2), 98\u2013103 (2008)","journal-title":"Inf. Process. Lett."},{"key":"11_CR5","first-page":"200","volume-title":"Proceedings of the Fourteenth Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA 2002","author":"P. Flocchini","year":"2002","unstructured":"Flocchini, P., Fraigniaud, P., Santoro, N.: Capture of an intruder by mobile agents. In: Proceedings of the Fourteenth Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA 2002, pp. 200\u2013209. ACM, New York (2002)"},{"issue":"1","key":"11_CR6","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1006\/inco.2001.3081","volume":"176","author":"M.A. Bender","year":"2002","unstructured":"Bender, M.A., Fernandez, A., Ron, D., Sahai, A., Vadhan, S.P.: The Power of a Pebble: Exploring and Mapping Directed Graphs. Inf. Comput.\u00a0176(1), 1\u201321 (2002)","journal-title":"Inf. Comput."},{"key":"11_CR7","first-page":"495","volume-title":"Proceedings of the 2009 IEEE International Conference on Robotics and Automation, ICRA 2009","author":"P. Brass","year":"2009","unstructured":"Brass, P., Gasparri, A., Cabrera-Mora, F., Xiao, J.: Multi-robot tree and graph exploration. In: Proceedings of the 2009 IEEE International Conference on Robotics and Automation, ICRA 2009, pp. 495\u2013500. IEEE Press, Piscataway (2009)"},{"issue":"4","key":"11_CR8","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1383369.1383378","volume":"4","author":"M. Bl\u00e4ser","year":"2008","unstructured":"Bl\u00e4ser, M.: A new approximation algorithm for the asymmetric TSP with triangle inequality. ACM Transactions on Algorithms 4(4), 47:1\u201347:15 (2008)","journal-title":"ACM Transactions on Algorithms"},{"key":"11_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":"11_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"232","DOI":"10.1007\/BFb0029571","volume-title":"Online Algorithms","author":"P. Bermann","year":"1998","unstructured":"Bermann, P.: On-line Searching and Navigation. In: Fiat, A., Woeginger, G.J. (eds.) Online Algorithms 1996. LNCS, vol.\u00a01442, pp. 232\u2013241. Springer, Heidelberg (1998)"},{"key":"11_CR11","first-page":"476","volume-title":"Proceedings of the 2000 IEEE International Conference on Robotics and Automation, ICRA 2000","author":"W. Burgard","year":"2000","unstructured":"Burgard, W., Moors, M., Fox, D., Simmons, R.G., Thrun, S.: Collaborative Multi-Robot Exploration. In: Proceedings of the 2000 IEEE International Conference on Robotics and Automation, ICRA 2000, pp. 476\u2013481. IEEE, San Francisco (2000)"},{"key":"11_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"208","DOI":"10.1007\/978-3-642-16926-7_20","volume-title":"Graph Theoretic Concepts in Computer Science","author":"J. Chalopin","year":"2010","unstructured":"Chalopin, J., Flocchini, P., Mans, B., Santoro, N.: Network Exploration by Silent and Oblivious Robots. In: Thilikos, D.M. (ed.) WG 2010. LNCS, vol.\u00a06410, pp. 208\u2013219. Springer, Heidelberg (2010)"},{"issue":"1-3","key":"11_CR13","doi-asserted-by":"publisher","first-page":"34","DOI":"10.1016\/j.tcs.2007.05.011","volume":"385","author":"S. Das","year":"2007","unstructured":"Das, S., Flocchini, P., Kutten, S., Nayak, A., Santoro, N.: Map construction of unknown graphs by multiple agents. Theor. Comput. Sci.\u00a0385(1-3), 34\u201348 (2007)","journal-title":"Theor. Comput. Sci."},{"key":"11_CR14","doi-asserted-by":"publisher","first-page":"355","DOI":"10.1109\/FSCS.1990.89554","volume-title":"Proceedings of the 31st Annual Symposium on Foundations of Computer Science, FOCS 1990","author":"X. Deng","year":"1990","unstructured":"Deng, X., Papadimitriou, C.H.: Exploring an unknown graph (Extended Abstract). In: Proceedings of the 31st Annual Symposium on Foundations of Computer Science, FOCS 1990, vol.\u00a0I, pp. 355\u2013361. IEEE Computer Society, St. Louis (1990)"},{"issue":"3","key":"11_CR15","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\u00a032(3), 265\u2013297 (1999)","journal-title":"J. Graph Theory"},{"key":"11_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1007\/978-3-642-31104-8_23","volume-title":"Structural Information and Communication Complexity","author":"S. Dobrev","year":"2012","unstructured":"Dobrev, S., Kr\u00e1lovic\u0306, R., Markou, E.: Online Graph Exploration with Advice. In: Even, G., Halld\u00f3rsson, M.M. (eds.) SIROCCO 2012. LNCS, vol.\u00a07355, pp. 267\u2013278. Springer, Heidelberg (2012)"},{"key":"11_CR17","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.\u00a04474, pp. 41\u201350. Springer, Heidelberg (2007)"},{"issue":"4","key":"11_CR18","doi-asserted-by":"publisher","first-page":"301","DOI":"10.1007\/s00453-002-1001-6","volume":"35","author":"L. Engebretsen","year":"2003","unstructured":"Engebretsen, L.: An Explicit Lower Bound for TSP with Distances One and Two. Algorithmica\u00a035(4), 301\u2013318 (2003)","journal-title":"Algorithmica"},{"key":"11_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"104","DOI":"10.1007\/978-3-540-74208-1_8","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"U. Feige","year":"2007","unstructured":"Feige, U., Singh, M.: Improved Approximation Ratios for Traveling Salesperson Tours and Paths in Directed Graphs. In: Charikar, M., Jansen, K., Reingold, O., Rolim, J.D.P. (eds.) APPROX and RANDOM 2007. LNCS, vol.\u00a04627, pp. 104\u2013118. Springer, Heidelberg (2007)"},{"key":"11_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"246","DOI":"10.1007\/978-3-540-24749-4_22","volume-title":"STACS 2004","author":"P. Fraigniaud","year":"2004","unstructured":"Fraigniaud, P., Ilcinkas, D.: Digraphs Exploration with Little Memory. In: Diekert, V., Habib, M. (eds.) STACS 2004. LNCS, vol.\u00a02996, pp. 246\u2013257. Springer, Heidelberg (2004)"},{"issue":"3","key":"11_CR21","doi-asserted-by":"publisher","first-page":"166","DOI":"10.1002\/net.20127","volume":"48","author":"P. Fraigniaud","year":"2006","unstructured":"Fraigniaud, P., Gasieniec, L., Kowalski, D.R., Pelc, A.: Collective tree exploration. Networks\u00a048(3), 166\u2013177 (2006)","journal-title":"Networks"},{"issue":"1","key":"11_CR22","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1002\/net.3230120103","volume":"12","author":"A.M. Frieze","year":"1982","unstructured":"Frieze, A.M., Galbiati, G., Maffioli, F.: On the worst-case performance of some algorithms for the asymmetric traveling salesman problem. Networks\u00a012(1), 23\u201339 (1982)","journal-title":"Networks"},{"issue":"3","key":"11_CR23","doi-asserted-by":"publisher","first-page":"881","DOI":"10.1137\/060662204","volume":"38","author":"R. Fleischer","year":"2008","unstructured":"Fleischer, R., Kamphans, T., Klein, R., Langetepe, E., Trippen, G.: Competitive Online Approximation of the Optimal Search Ratio. SIAM J. Comput.\u00a038(3), 881\u2013898 (2008)","journal-title":"SIAM J. Comput."},{"key":"11_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"120","DOI":"10.1007\/3-540-44867-5_10","volume-title":"Experimental and Efficient Algorithms","author":"R. Fleischer","year":"2003","unstructured":"Fleischer, R., Trippen, G.: Experimental Studies of Graph Traversal Algorithms. In: Jansen, K., Margraf, M., Mastrolli, M., Rolim, J.D.P. (eds.) WEA 2003. LNCS, vol.\u00a02647, pp. 120\u2013133. Springer, Heidelberg (2003)"},{"key":"11_CR25","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)"},{"issue":"1","key":"11_CR26","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. Oper. Res. Lett.\u00a032(1), 1\u20134 (2004)","journal-title":"Oper. Res. Lett."},{"issue":"1","key":"11_CR27","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":"11_CR28","doi-asserted-by":"publisher","first-page":"56","DOI":"10.1109\/SFCS.2003.1238181","volume-title":"Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2003","author":"H. Kaplan","year":"2003","unstructured":"Kaplan, H., Lewenstein, M., Shafrir, N., Sviridenko, M.: Approximation Algorithms for Asymmetric TSP by Decomposing Directed Regular Multigraphs. In: Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2003, pp. 56\u201365. IEEE Computer Society, Washington, DC (2003)"},{"key":"11_CR29","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"416","DOI":"10.1007\/978-3-642-24100-0_40","volume-title":"Distributed Computing","author":"F. Kuhn","year":"2011","unstructured":"Kuhn, F., Oshman, R.: The Complexity of Data Aggregation in Directed Networks. In: Peleg, D. (ed.) DISC 2011. LNCS, vol.\u00a06950, pp. 416\u2013431. Springer, Heidelberg (2011)"},{"key":"11_CR30","unstructured":"Kutten, S.: Stepwise construction of an efficient distributed traversing algorithm for general strongly connected directed networks or: Traversing one way streets with no map. In: Computer Communication Technologies for the 90\u2019s, Proceedings of the Ninth International Conference on Computer Communication, ICCC 1988, pp. 446\u2013452. International Council for Computer Communication, Elsevier (1988)"},{"key":"11_CR31","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"478","DOI":"10.1007\/978-3-642-22012-8_38","volume-title":"Automata, Languages and Programming","author":"N. Megow","year":"2011","unstructured":"Megow, N., Mehlhorn, K., Schweitzer, P.: Online Graph Exploration: New Results on Old and New Algorithms. In: Aceto, L., Henzinger, M., Sgall, J. (eds.) ICALP 2011, Part II. LNCS, vol.\u00a06756, pp. 478\u2013489. Springer, Heidelberg (2011)"},{"issue":"9","key":"11_CR32","doi-asserted-by":"crossref","first-page":"1620","DOI":"10.1587\/transinf.E92.D.1620","volume":"92-D","author":"S. Miyazaki","year":"2009","unstructured":"Miyazaki, S., Morimoto, N., Okabe, Y.: The Online Graph Exploration Problem on Restricted Graphs. IEICE Transactions\u00a092-D(9), 1620\u20131627 (2009)","journal-title":"IEICE Transactions"},{"key":"11_CR33","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1145\/313239.313263","volume-title":"Proceedings of the 3rd International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications, DIALM 1999","author":"R. Prakash","year":"1999","unstructured":"Prakash, R.: Unidirectional links prove costly in wireless ad hoc networks. In: Proceedings of the 3rd International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications, DIALM 1999, pp. 15\u201322. ACM, New York (1999)"},{"key":"11_CR34","doi-asserted-by":"publisher","first-page":"1692","DOI":"10.1109\/INFCOM.2012.6195540","volume-title":"Proceedings of the IEEE INFOCOM 2012","author":"B.F. Ribeiro","year":"2012","unstructured":"Ribeiro, B.F., Wang, P., Murai, F., Towsley, D.: Sampling directed graphs with random walks. In: Proceedings of the IEEE INFOCOM 2012, pp. 1692\u20131700. IEEE, Orlando (2012)"},{"issue":"3","key":"11_CR35","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."},{"issue":"1","key":"11_CR36","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1007\/BF01840435","volume":"1","author":"R. Sedgewick","year":"1986","unstructured":"Sedgewick, R., Vitter, J.S.: Shortest Paths in Euclidean Graphs. Algorithmica\u00a01(1), 31\u201348 (1986)","journal-title":"Algorithmica"},{"issue":"6","key":"11_CR37","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1016\/0020-0190(92)90103-3","volume":"44","author":"S. Vishwanathan","year":"1992","unstructured":"Vishwanathan, S.: An Approximation Algorithm for the Asymmetric Travelling Salesman Problem with Distances One and Two. Inf. Process. Lett.\u00a044(6), 297\u2013302 (1992)","journal-title":"Inf. Process. Lett."}],"container-title":["Lecture Notes in Computer Science","Principles of Distributed Systems"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-35476-2_11.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,4]],"date-time":"2021-05-04T09:17:35Z","timestamp":1620119855000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-35476-2_11"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642354755","9783642354762"],"references-count":37,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-35476-2_11","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}