{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T22:40:02Z","timestamp":1742596802305,"version":"3.40.2"},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540569398"},{"type":"electronic","value":"9783540478263"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1993]]},"DOI":"10.1007\/3-540-56939-1_65","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T11:57:31Z","timestamp":1330257451000},"page":"102-113","source":"Crossref","is-referenced-by-count":7,"title":["Constructing competitive tours from local information"],"prefix":"10.1007","author":[{"given":"Bala","family":"Kalyanasundaram","sequence":"first","affiliation":[]},{"given":"Kirk R.","family":"Pruhs","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,5,28]]},"reference":[{"key":"9_CR1","doi-asserted-by":"crossref","unstructured":"N. Alon, and Y. Azar, On-line Steiner trees in the Euclidean plane, in: Proceedings of the 8th ACM Symposium on Computational Geometry (1992).","DOI":"10.1145\/142675.142744"},{"key":"9_CR2","unstructured":"R. Baeza-Yates, J. Culberson, and G. Rawlins, Searching with uncertainty, to appear in: Information and Computation."},{"key":"9_CR3","unstructured":"V. Bafna, B. Kalyanasundaram, and K. Pruhs, Not all insertion methods yield constant approximate tours in the plane, Technical Report, Computer Science Department, University of Pittsburgh, 1992."},{"key":"9_CR4","unstructured":"A. Bar-Noy, and B. Schieber, The Canadian travelers problem, in: Proceedings of the Second Annual ACM\/SIAM Symposium on Discrete Algorithms (1991) 261\u2013270."},{"key":"9_CR5","doi-asserted-by":"crossref","unstructured":"A. Blum, P. Raghavan, and B. Schieber, Navigating in unfamiliar geometric terrain, in: Proceedings of the Twenty Third Annual ACM Symposium of Theory of Computing (1991) 494\u2013504.","DOI":"10.1145\/103418.103419"},{"key":"9_CR6","unstructured":"B. Chandra, and S. Vishwanathan, Constructing reliable communication networks of small weight online, Manuscript."},{"key":"9_CR7","doi-asserted-by":"crossref","unstructured":"G. Das and D. Joseph, Which triangulations approximate the complete graph, in: Proceedings of International Symposium on Optimal Algorithms (1989) 168\u2013192.","DOI":"10.1007\/3-540-51859-2_15"},{"key":"9_CR8","doi-asserted-by":"crossref","unstructured":"X. Deng, and C. Papadimitriou, Exploring an unknown graph, in: Proceedings of the Thirty First Annual Symposium on Foundations of Computer Science (1990) 355\u2013361.","DOI":"10.1109\/FSCS.1990.89554"},{"key":"9_CR9","doi-asserted-by":"crossref","unstructured":"X. Deng, Kameda, and C. Papadimitriou, How to learn an unknown environment, in: Proceedings of the Thirty Second Annual Symposium on Foundations of Computer Science (1991), 298\u2013303.","DOI":"10.1109\/SFCS.1991.185382"},{"key":"9_CR10","doi-asserted-by":"crossref","first-page":"369","DOI":"10.1137\/0404033","volume":"4","author":"M. Imase","year":"1991","unstructured":"M. Imase, and B. Waxman, Dynamic Steiner tree problem, SIAM Journal of Discrete Mathematics 4 (1991) 369\u2013384.","journal-title":"SIAM Journal of Discrete Mathematics"},{"key":"9_CR11","doi-asserted-by":"crossref","unstructured":"E. Jennings, and A. Lingas, On the Relationships among Constrained Geometric Structures, Proceedings of the 3rd International Symposium, on Algorithms and Computation (ISAAC((1992) 289\u2013298.","DOI":"10.1007\/3-540-56279-6_82"},{"key":"9_CR12","doi-asserted-by":"crossref","unstructured":"B. Kalyanasundaram, and K. Pruhs, Constructing competitive tours from local information, Technical Report, Computer Science Department, University of Pittsburgh, 1992.","DOI":"10.1007\/3-540-56939-1_65"},{"key":"9_CR13","doi-asserted-by":"crossref","unstructured":"B. Kalyanasundaram, and K. Pruhs, A competitive analysis of nearest neighbor algorithms for searching unknown scenes, in: Proceedings of the 9th Annual Symposium on Theoretical Aspects of Computer Science (1992) 147\u2013157.","DOI":"10.1007\/3-540-55210-3_180"},{"key":"9_CR14","doi-asserted-by":"crossref","unstructured":"R. Klein, Walking an unknown street with bounded detour, in: Proceedings of the Thirty Second Annual Symposium on Foundations of Computer Science (1991) 304\u2013313.","DOI":"10.1109\/SFCS.1991.185383"},{"key":"9_CR15","volume-title":"The Traveling Salesman Problem","author":"E. Lawler","year":"1985","unstructured":"E. Lawler, J. Lenstra, A. Rinnooy Kan, and D. Schmoys, The Traveling Salesman Problem (Wiley, New York, 1985)."},{"key":"9_CR16","doi-asserted-by":"crossref","unstructured":"C. Levcopoulos, and A. Lingas, There are planar graphs almost as good as the complete graphs and as short as minimum spanning trees, in: Proceedings of International Symposium on Optimal Algorithms (1989) 9\u201313.","DOI":"10.1007\/3-540-51859-2_2"},{"key":"9_CR17","doi-asserted-by":"crossref","unstructured":"C. Papadimitriou, and M. Yannakakis, Shortest paths without a map, in: Proceedings of the Sixteenth Annual Internation Colloquium on Automata, Languages, and Programming (1989) 610\u2013620.","DOI":"10.1007\/BFb0035787"},{"key":"9_CR18","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-1098-6","volume-title":"Computational Geometry: An Introduction","author":"F. Preparata","year":"1985","unstructured":"F. Preparata, and M. Shamos, Computational Geometry: An Introduction (Springer-Verlag, New York, 1985)."},{"key":"9_CR19","doi-asserted-by":"crossref","first-page":"563","DOI":"10.1137\/0206041","volume":"6","author":"D. Rosenkrantz","year":"1977","unstructured":"D. Rosenkrantz, R. Stearns, and P. Lewis, An analysis of several heuristics for the traveling salesman problem, SIAM Journal of Computing 6 (1977) 563\u2013581.","journal-title":"SIAM Journal of Computing"},{"issue":"3","key":"9_CR20","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1016\/0031-3203(91)90064-C","volume":"24","author":"T. H. Su","year":"1991","unstructured":"T. H. Su, and R.C. Chang, Computing the constrained relative neighborhood graphs and constrained Gabriel graphs in Euclidean Plane, in: Pattern Recognition 24, 3, (1991) 221\u2013230.","journal-title":"Pattern Recognition"},{"key":"9_CR21","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1016\/0031-3203(80)90066-7","volume":"12","author":"G. Toussaint","year":"1980","unstructured":"G. Toussaint, The relative neighborhood graph of a finite planar set, Pattern Recognition 12 (1980) 261\u2013268.","journal-title":"Pattern Recognition"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-56939-1_65.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T21:58:20Z","timestamp":1742594300000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-56939-1_65"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1993]]},"ISBN":["9783540569398","9783540478263"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/3-540-56939-1_65","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1993]]}}}