{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,10]],"date-time":"2026-04-10T03:25:29Z","timestamp":1775791529058,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540614401","type":"print"},{"value":"9783540685807","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1996]]},"DOI":"10.1007\/3-540-61440-0_135","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T21:37:54Z","timestamp":1330292274000},"page":"280-289","source":"Crossref","is-referenced-by-count":52,"title":["Searching a fixed graph"],"prefix":"10.1007","author":[{"given":"Elias","family":"Koutsoupias","sequence":"first","affiliation":[]},{"given":"Christos","family":"Papadimitriou","sequence":"additional","affiliation":[]},{"given":"Mihalis","family":"Yannakakis","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,2]]},"reference":[{"issue":"1","key":"23_CR1","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1051\/ita\/1986200100791","volume":"20","author":"F. Afrati","year":"1986","unstructured":"F. Afrati, S. Cosmadakis, C. H. Papadimitriou, G. Papageorgiou, and N. Papakostantinou. The complexity of the travelling repairman problem. Informatique The\u00f3rique et Applications, 20(1):79\u201387, 1986.","journal-title":"Informatique The\u00f3rique et Applications"},{"key":"23_CR2","doi-asserted-by":"crossref","unstructured":"R.A. Baeza-Yates, J.C. Culberson, and G.J.E. Rawlins. Searching with uncertainty. SWAT 88. 1st Scandinavian Workshop on Algorithm Theory. Proceedings, pages 176\u201389, 1988.","DOI":"10.1007\/3-540-19487-8_20"},{"key":"23_CR3","doi-asserted-by":"crossref","unstructured":"A. Blum, P. Chalasani, D. Coppersmith, W. Pulleyblank, P. Raghavan, and M. Sudan. The minimum latency problem. Proceedings 26th Annual Symposium on Theory of Computing, pages 163\u2013171, 1994.","DOI":"10.1145\/195058.195125"},{"key":"23_CR4","unstructured":"N. Christofides. Worst-case analysis of a new heuristic for the traveling salesman problem. Technical report, GSIA, Carnegie-Mellon University, 1976."},{"key":"23_CR5","doi-asserted-by":"crossref","unstructured":"X. Deng, T. Kameda, and C. Papadimitriou. How to learn an unknown environment. Proceedings 32nd Annual Symposium on Foundations of Computer Science, pages 298\u2013303, 1991.","DOI":"10.1109\/SFCS.1991.185382"},{"key":"23_CR6","doi-asserted-by":"crossref","first-page":"355","DOI":"10.1109\/FSCS.1990.89554","volume":"1","author":"X. Deng","year":"1990","unstructured":"X. Deng and C. H. Papadimitriou. Exploring an unknown graph. Proceedings 31st Annual Symposium on Foundations of Computer Science, pages 355\u2013361 vol. 1, 1990.","journal-title":"Proceedings 31st Annual Symposium on Foundations of Computer Science"},{"key":"23_CR7","doi-asserted-by":"crossref","first-page":"1055","DOI":"10.1287\/opre.41.6.1055","volume":"41","author":"M. Fischetti","year":"1993","unstructured":"M. Fischetti, G. Laporte, and M. Martello. The delivery man problem and cumulative matroids. Operations Research, vol. 41, pages 1055\u20131064, 1993.","journal-title":"Operations Research"},{"key":"23_CR8","unstructured":"M. Goemans and J. Kleinberg. An improved approximation ratio for the minimum latency problem. Proceedings Annual Symposium on Discrete Algorithms, to appear, 1996."},{"key":"23_CR9","doi-asserted-by":"crossref","unstructured":"M. Gr\u00f6tschel, L. Lov\u00e1sz, and A. Schrijver. Geometric algorithms and combinatorial optimization. Springer-Verlag, 1988.","DOI":"10.1007\/978-3-642-97881-4"},{"key":"23_CR10","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1007\/BF02097807","volume":"18","author":"E. Minieka","year":"1989","unstructured":"E. Minieka. The delivery man problem on a tree network. Annals of Operations Research, vol. 18, pages 261\u2013266, 1989.","journal-title":"Annals of Operations Research"},{"key":"23_CR11","doi-asserted-by":"crossref","unstructured":"S.A. Plotkin, D.B. Shmoys, and \u00c9. Tardos. Fast approximation algorithms for fractional packing and covering problems. Proceedings 32nd Annual Symposium on Foundations of Computer Science, pages 495\u2013504, 1991.","DOI":"10.1109\/SFCS.1991.185411"},{"issue":"1","key":"23_CR12","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1016\/0304-3975(91)90263-2","volume":"84","author":"C. H. Papadimitriou","year":"1991","unstructured":"C. H. Papadimitriou and M. Yannakakis. Shortest paths without a map. Theoretical Computer Science, 84(1):127\u201350, July 1991.","journal-title":"Theoretical Computer Science"},{"issue":"1","key":"23_CR13","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1287\/moor.18.1.1","volume":"18","author":"C. H. Papadimitriou","year":"1993","unstructured":"C. H. Papadimitriou and M. Yannakakis. The traveling salesman problem with distances one and two. Mathematics of Operations Research, 18(1):1\u201311, February 1993.","journal-title":"Mathematics of Operations Research"},{"issue":"2","key":"23_CR14","doi-asserted-by":"publisher","first-page":"202","DOI":"10.1145\/2786.2793","volume":"28","author":"D. D. Sleator","year":"1985","unstructured":"D. D. Sleator and R. E. Tarjan. Amortized efficiency of list update and paging rules. Communications of the ACM, 28(2):202\u20138, February 1985.","journal-title":"Communications of the ACM"},{"key":"23_CR15","unstructured":"\u00c9. Tardos. Private communication, 1995."},{"key":"23_CR16","unstructured":"D. West. Private communication, 1995."},{"key":"23_CR17","unstructured":"T. G. Will. Extremal Results and Algorithms for Degree Sequences of Graphs. PhD thesis, U. of Illinois at Urbana-Champaign, 1993."}],"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-61440-0_135.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T21:06:15Z","timestamp":1605647175000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-61440-0_135"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996]]},"ISBN":["9783540614401","9783540685807"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/3-540-61440-0_135","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1996]]}}}