{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,9,13]],"date-time":"2023-09-13T19:45:32Z","timestamp":1694634332110},"reference-count":22,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2008,10,9]],"date-time":"2008-10-09T00:00:00Z","timestamp":1223510400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2010,8]]},"DOI":"10.1007\/s00453-008-9228-5","type":"journal-article","created":{"date-parts":[[2008,10,8]],"date-time":"2008-10-08T16:57:48Z","timestamp":1223485068000},"page":"668-688","source":"Crossref","is-referenced-by-count":1,"title":["Approximate Shortest Paths Guided by a Small Index"],"prefix":"10.1007","volume":"57","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","published-online":{"date-parts":[[2008,10,9]]},"reference":[{"key":"9228_CR1","volume-title":"The Probabilistic Method","author":"N. Alon","year":"1992","unstructured":"Alon, N., Spencer, J.: The Probabilistic Method. Wiley, New York (1992)"},{"issue":"1","key":"9228_CR2","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1007\/BF02189308","volume":"9","author":"I. Alth\u00f6fer","year":"1993","unstructured":"Alth\u00f6fer, I., Das, G., Dobkin, D.P., Joseph, D., Soares, J.: On sparse spanners of weighted graphs. Discrete Comput. Geom. 9(1), 81\u2013100 (1993)","journal-title":"Discrete Comput. Geom."},{"key":"9228_CR3","unstructured":"Baswana, S., Sen, S.: Approximate distance oracles for unweighted graphs in $\\tilde{O}(n^{2})$ time. In: J.I.\u00a0Munro (ed.) Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp.\u00a0271\u2013280 (2004)"},{"key":"9228_CR4","volume-title":"Extremal Graph Theory","author":"B. Bollob\u00e1s","year":"1978","unstructured":"Bollob\u00e1s, B.: Extremal Graph Theory. Academic Press, San Diego (1978)"},{"key":"9228_CR5","doi-asserted-by":"crossref","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. Math. Oper. Res. 4, 233\u2013235 (1979)","journal-title":"Math. Oper. Res."},{"issue":"5","key":"9228_CR6","doi-asserted-by":"crossref","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 J. Comput. 32(5), 1338\u20131355 (2003)","journal-title":"SIAM J. Comput."},{"key":"9228_CR7","doi-asserted-by":"crossref","unstructured":"Demetrescu, C., Finocchi, I., Ribichini, A.: Trading off space for passes in graph streaming problems. In: Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 714\u2013723 (2006)","DOI":"10.1145\/1109557.1109635"},{"key":"9228_CR8","unstructured":"Demetrescu, C., Goldberg, A., Johnson, D. (eds.): 9th DIMACS Challenge on Shortest Paths (to appear). Available at http:\/\/www.dis.uniroma1.it\/~challenge9"},{"key":"9228_CR9","doi-asserted-by":"crossref","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. Numer. Math. 1, 269\u2013271 (1959)","journal-title":"Numer. Math."},{"key":"9228_CR10","first-page":"745","volume-title":"Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms","author":"J. Feigenbaum","year":"2005","unstructured":"Feigenbaum, J., Kannan, S., McGregor, A., Suri, S., Zhang, J.: Graph distances in the streaming model: the value of space. In: Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 745\u2013754. SIAM, Philadelphia (2005)"},{"key":"9228_CR11","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":"9228_CR12","unstructured":"Goldberg, A., Harrelson, C.: Computing the shortest path: A* search meets graph theory. In: Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, vol. 16 (2005)"},{"key":"9228_CR13","series-title":"Lecture Notes in Computer Science","first-page":"62","volume-title":"Algorithms for Memory Hierarchies","author":"I. Katriel","year":"2002","unstructured":"Katriel, I., Meyer, U.: Elementary graph algorithms in external memory. In: Meyer, U., Sanders, P., Sibeyn, J.F. (eds.) Algorithms for Memory Hierarchies. Lecture Notes in Computer Science, vol. 2625, pp. 62\u201384. Springer, Berlin (2002)"},{"key":"9228_CR14","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":"Proceedings of the 11th Annual European Symposium on Algorithms","author":"U. Meyer","year":"2003","unstructured":"Meyer, U., Zeh, N.: I\/O-efficient undirected shortest paths. In: Battista, G.D., Zwick, U. (eds.) Proceedings of the 11th Annual European Symposium on Algorithms. Lecture Notes in Computer Science, vol. 2832, pp. 434\u2013445. Springer, Berlin (2003)"},{"issue":"1","key":"9228_CR15","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1002\/jgt.3190130114","volume":"13","author":"D. Peleg","year":"1989","unstructured":"Peleg, D., Sch\u00e4ffer, A.A.: Graph spanners. J. Graph Theory 13(1), 99\u2013116 (1989)","journal-title":"J. Graph Theory"},{"key":"9228_CR16","first-page":"742","volume":"27","author":"H. Pr\u00fcfer","year":"1918","unstructured":"Pr\u00fcfer, H.: Neuer Beweis eines Satzes \u00fcber Permutationen. Arch. Math. Phys. 27, 742\u2013744 (1918)","journal-title":"Arch. Math. Phys."},{"key":"9228_CR17","unstructured":"Regev, H.: The weight of the greedy graph spanner. Technical Report CS95-22, Weizmann Institute of Science, July 1995"},{"key":"9228_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"568","DOI":"10.1007\/11561071_51","volume-title":"Proceedings of the 13th Annual European Symposium on Algorithms","author":"P. Sanders","year":"2005","unstructured":"Sanders, P., Schultes, D.: Highway hierarchies hasten exact shortest path queries. In: Brodal, G.S., Leonardi, S. (eds.) Proceedings of the 13th Annual European Symposium on Algorithms. Lecture Notes in Computer Science, vol. 3669, pp. 568\u2013579. Springer, Berlin (2005)"},{"key":"9228_CR19","unstructured":"Stirling, J.: Methodus Differentialis. London (1730)"},{"key":"9228_CR20","doi-asserted-by":"crossref","first-page":"183","DOI":"10.1145\/380752.380798","volume-title":"Proceedings of the Thirty-Third Annual ACM Symposium on Theory of Computing","author":"M. Thorup","year":"2001","unstructured":"Thorup, M., Zwick, U.: Approximate distance oracles. In: Proceedings of the Thirty-Third Annual ACM Symposium on Theory of Computing, pp. 183\u2013192. Assoc. Comput. Mach. Press, New York (2001)"},{"issue":"1","key":"9228_CR21","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1044731.1044732","volume":"52","author":"M. Thorup","year":"2005","unstructured":"Thorup, M., Zwick, U.: Approximate distance oracles. J. ACM 52(1), 1\u201324 (2005)","journal-title":"J. ACM"},{"key":"9228_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1007\/3-540-44676-1_3","volume-title":"Proceedings of the 9th Annual European Symposium on Algorithms","author":"U. Zwick","year":"2001","unstructured":"Zwick, U.: Exact and approximate distances in graphs\u2014a survey. In: auf der Heide, F.M. (ed.) Proceedings of the 9th Annual European Symposium on Algorithms. Lecture Notes in Computer Science, vol. 2161, pp. 33\u201348. Springer, Berlin (2001)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-008-9228-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-008-9228-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-008-9228-5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,9,18]],"date-time":"2021-09-18T05:03:59Z","timestamp":1631941439000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-008-9228-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,10,9]]},"references-count":22,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2010,8]]}},"alternative-id":["9228"],"URL":"https:\/\/doi.org\/10.1007\/s00453-008-9228-5","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,10,9]]}}}