{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T22:43:38Z","timestamp":1725489818052},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540739487"},{"type":"electronic","value":"9783540739517"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-73951-7_48","type":"book-chapter","created":{"date-parts":[[2007,8,20]],"date-time":"2007-08-20T06:18:03Z","timestamp":1187590683000},"page":"553-564","source":"Crossref","is-referenced-by-count":0,"title":["Approximate Shortest Paths Guided by a Small Index"],"prefix":"10.1007","author":[{"given":"J\u00f6rg","family":"Derungs","sequence":"first","affiliation":[]},{"given":"Riko","family":"Jacob","sequence":"additional","affiliation":[]},{"given":"Peter","family":"Widmayer","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"1","key":"48_CR1","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1145\/1044731.1044733","volume":"52","author":"L. Aleksandrov","year":"2005","unstructured":"Aleksandrov, L., Maheshwari, A., Sack, J.-R.: Determining approximate shortest paths on weighted polyhedral surfaces. Journal of the ACM\u00a052(1), 25\u201353 (2005)","journal-title":"Journal of the ACM"},{"key":"48_CR2","volume-title":"The Probabilistic Method","author":"N. Alon","year":"1992","unstructured":"Alon, N., Spencer, J.: The Probabilistic Method. John Wiley, New York (1992)"},{"key":"48_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"26","DOI":"10.1007\/3-540-52846-6_75","volume-title":"SWAT \u201990","author":"I. Alth\u00f6fer","year":"1990","unstructured":"Alth\u00f6fer, I., Das, G., Dobkin, D.P., Joseph, D.: Generating sparse spanners for weighted graphs. In: Gilbert, J.R., Karlsson, R. (eds.) SWAT 1990. LNCS, vol.\u00a0447, pp. 26\u201337. Springer, Heidelberg (1990)"},{"key":"48_CR4","unstructured":"Baswana, S., Sen, S.: Approximate distance oracles for unweighted graphs in \u00d5 (n 2) time. In: SODA 2004, pp. 271\u2013280 (2004)"},{"key":"48_CR5","volume-title":"Extremal Graph Theory","author":"B. Bollob\u00e1s","year":"1978","unstructured":"Bollob\u00e1s, B.: Extremal Graph Theory. Academic Press, San Diego (1978)"},{"key":"48_CR6","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1287\/moor.4.3.233","volume":"4","author":"V. Chv\u00e1tal","year":"1979","unstructured":"Chv\u00e1tal, V.: A greedy heuristic for the set-covering problem. Mathematics of Operations Research\u00a04, 233\u2013235 (1979)","journal-title":"Mathematics of Operations Research"},{"issue":"5","key":"48_CR7","doi-asserted-by":"publisher","first-page":"1338","DOI":"10.1137\/S0097539702403098","volume":"32","author":"E. Cohen","year":"2003","unstructured":"Cohen, E., Halperin, E., Kaplan, H., Zwick, U.: Reachability and distance queries via 2-hop labels. SIAM Journal on Computing\u00a032(5), 1338\u20131355 (2003)","journal-title":"SIAM Journal on Computing"},{"key":"48_CR8","doi-asserted-by":"crossref","unstructured":"Demetrescu, C., Finocchi, I., Ribichini, A.: Trading off space for passes in graph streaming problems. In: SODA 2006, pp. 714\u2013723 (2006)","DOI":"10.1145\/1109557.1109635"},{"key":"48_CR9","unstructured":"Demetrescu, C., Goldberg, A., Johnson, D. (eds.): 9th DIMACS Challenge on Shortest Paths, available at http:\/\/www.dis.uniroma1.it\/~challenge9 (to appear)"},{"key":"48_CR10","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1007\/BF01386390","volume":"1","author":"E.W. Dijkstra","year":"1959","unstructured":"Dijkstra, E.W.: A note on two problems in connection with graphs. Numerische Mathematik\u00a01, 269\u2013271 (1959)","journal-title":"Numerische Mathematik"},{"key":"48_CR11","unstructured":"Feigenbaum, J., Kannan, S., McGregor, A., Suri, S., Zhang, J.: Graph distances in the streaming model: the value of space. In: SODA 2005, pp. 745\u2013754 (2005)"},{"key":"48_CR12","volume-title":"Computer and Intractability: A Guide to the Theory of NP-Completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computer and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, New York (1979)"},{"key":"48_CR13","unstructured":"Goldberg, A.V., Harrelson, C.: Computing the shortest path: A* search meets graph theory. In: SODA 2005, vol. 16, pp. 156\u2013165 (2005)"},{"key":"48_CR14","doi-asserted-by":"crossref","unstructured":"Katriel, I., Meyer, U.: Elementary graph algorithms in external memory. In: Algorithms for Memory Hierarchies, pp. 62\u201384 (2002)","DOI":"10.1007\/3-540-36574-5_4"},{"key":"48_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"434","DOI":"10.1007\/978-3-540-39658-1_40","volume-title":"Algorithms - ESA 2003","author":"U. Meyer","year":"2003","unstructured":"Meyer, U., Zeh, N.: I\/O-efficient undirected shortest paths. In: Di Battista, G., Zwick, U. (eds.) ESA 2003. LNCS, vol.\u00a02832, pp. 434\u2013445. Springer, Heidelberg (2003)"},{"issue":"1","key":"48_CR16","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1002\/jgt.3190130114","volume":"13","author":"D. Peleg","year":"1989","unstructured":"Peleg, D., Sch\u00e4ffer, A.A.: Graph spanners. Journal of Graph Theory\u00a013(1), 99\u2013116 (1989)","journal-title":"Journal of Graph Theory"},{"key":"48_CR17","first-page":"742","volume":"27","author":"H. Pr\u00fcfer","year":"1918","unstructured":"Pr\u00fcfer, H.: Neuer Beweis eines Satzes \u00fcber Permutationen. Arch. Math. Phys.\u00a027, 742\u2013744 (1918)","journal-title":"Arch. Math. Phys."},{"key":"48_CR18","unstructured":"Regev, H.: The weight of the greedy graph spanner. Technical Report CS95-22, Weizmann Institute Of Science (July 1995)"},{"key":"48_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"568","DOI":"10.1007\/11561071_51","volume-title":"Algorithms \u2013 ESA 2005","author":"P. Sanders","year":"2005","unstructured":"Sanders, P., Schultes, D.: Highway hierarchies hasten exact shortest path queries. In: Brodal, G.S., Leonardi, S. (eds.) ESA 2005. LNCS, vol.\u00a03669, pp. 568\u2013579. Springer, Heidelberg (2005)"},{"issue":"1","key":"48_CR20","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1044731.1044732","volume":"52","author":"M. Thorup","year":"2005","unstructured":"Thorup, M., Zwick, U.: Approximate distance oracles. Journal of the ACM\u00a052(1), 1\u201324 (2005)","journal-title":"Journal of the ACM"},{"key":"48_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1007\/3-540-44676-1_3","volume-title":"Algorithms - ESA 2001","author":"U. Zwick","year":"2001","unstructured":"Zwick, U.: Exact and approximate distances in graphs - a survey. In: Meyer auf der Heide, F. (ed.) ESA 2001. LNCS, vol.\u00a02161, pp. 33\u201348. Springer, Heidelberg (2001)"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Data Structures"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-73951-7_48.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T06:06:02Z","timestamp":1619503562000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-73951-7_48"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540739487","9783540739517"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-73951-7_48","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[]}}