{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,11]],"date-time":"2026-03-11T15:52:04Z","timestamp":1773244324419,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":38,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540709176","type":"print"},{"value":"9783540709183","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-70918-3_3","type":"book-chapter","created":{"date-parts":[[2007,5,23]],"date-time":"2007-05-23T23:41:23Z","timestamp":1179963683000},"page":"23-36","source":"Crossref","is-referenced-by-count":35,"title":["Speed-Up Techniques for Shortest-Path Computations"],"prefix":"10.1007","author":[{"given":"Dorothea","family":"Wagner","sequence":"first","affiliation":[]},{"given":"Thomas","family":"Willhalm","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"3_CR1","doi-asserted-by":"crossref","unstructured":"Bast, H., et al. In Transit to Constant Shortest-Path Queries in Road Networks. In: Proc. Algorithm Engineering and Experiments (ALENEX\u201907), SIAM, to appear (2007)","DOI":"10.1137\/1.9781611972870.5"},{"key":"3_CR2","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1287\/mnsc.6.2.187","volume":"6","author":"G. Dantzig","year":"1960","unstructured":"Dantzig, G.: On the shortest route through a network. Mgnt. Sci.\u00a06, 187\u2013190 (1960)","journal-title":"Mgnt. Sci."},{"key":"3_CR3","unstructured":"Delling, D., et al.: Highway Hierarchies Star. In: 9th DIMACS Implementation Challenge - Shortest Paths. http:\/\/www.dis.uniroma1.it\/~challenge9\/papers.shtml"},{"key":"3_CR4","unstructured":"Delling, D., et al.: High-Performance Multi-Level Graphs. In: 9th DIMACS Implementation Challenge - Shortest Paths. http:\/\/www.dis.uniroma1.it\/~challenge9\/papers.shtml"},{"key":"3_CR5","doi-asserted-by":"publisher","first-page":"632","DOI":"10.1145\/363269.363610","volume":"12","author":"R. Dial","year":"1969","unstructured":"Dial, R.: Algorithm 360: Shortest path forest with topological ordering. Communications of ACM\u00a012, 632\u2013633 (1969)","journal-title":"Communications of ACM"},{"key":"3_CR6","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 connexion with graphs. Numerische Mathematik\u00a01, 269\u2013271 (1959)","journal-title":"Numerische Mathematik"},{"key":"3_CR7","unstructured":"9th DIMACS Implementation Challenge - Shortest Paths. http:\/\/www.dis.uniroma1.it\/~challenge9\/papers.shtml"},{"key":"3_CR8","doi-asserted-by":"publisher","first-page":"596","DOI":"10.1145\/28869.28874","volume":"34","author":"M.L. Fredman","year":"1987","unstructured":"Fredman, M.L., Tarjan, R.E.: Fibonacci heaps and their uses in improved network optimization algorithms. Journal of the ACM (JACM)\u00a034, 596\u2013615 (1987)","journal-title":"Journal of the ACM (JACM)"},{"key":"3_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"502","DOI":"10.1007\/3-540-45678-3_43","volume-title":"Algorithms and Computation","author":"A.V. Goldberg","year":"2001","unstructured":"Goldberg, A.V.: Shortest path algorithms: Engineering aspects. In: Eades, P., Takaoka, T. (eds.) ISAAC 2001. LNCS, vol.\u00a02223, pp. 502\u2013513. Springer, Heidelberg (2001)"},{"key":"3_CR10","first-page":"156","volume-title":"Proc. 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA \u201905)","author":"A.V. Goldberg","year":"2005","unstructured":"Goldberg, A.V., Harrelson, C.: Computing the shortest path: A * search meets graph theory. In: Proc. 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA \u201905), pp. 156\u2013165. ACM Press, New York (2005)"},{"key":"3_CR11","first-page":"129","volume-title":"Proc. Algorithm Engineering and Experiments (ALENEX\u201906)","author":"A.V. Goldberg","year":"2006","unstructured":"Goldberg, A.V., Kaplan, H., Werneck, R.: Reach for A *: Efficient point-to-point shortest path algorithms. In: Raman, R., Stallmann, M. (eds.) Proc. Algorithm Engineering and Experiments (ALENEX\u201906), pp. 129\u2013143. SIAM, Philadelphia (2006)"},{"key":"3_CR12","unstructured":"Goldberg, A.V., Kaplan, H., Werneck, R.: Better Landmarks within Reach. In: 9th DIMACS Implementation Challenge - Shortest Paths. http:\/\/www.dis.uniroma1.it\/~challenge9\/papers.shtml"},{"key":"3_CR13","first-page":"100","volume-title":"Proc. Algorithm Engineering and Experiments (ALENEX\u201904)","author":"R. Gutman","year":"2004","unstructured":"Gutman, R.: Reach-based routing: A new approach to shortest path algortihms optimized for road networks. In: Arge, L., Italiano, G.F., Sedgewick, R. (eds.) Proc. Algorithm Engineering and Experiments (ALENEX\u201904), pp. 100\u2013111. SIAM, Philadelphia (2004)"},{"key":"3_CR14","doi-asserted-by":"crossref","first-page":"179","DOI":"10.7155\/jgaa.00051","volume":"6","author":"D. Harel","year":"2002","unstructured":"Harel, D., Koren, Y.: A fast multi-scale method for drawing large graphs. Journal of graph algorithms and applications\u00a06, 179\u2013202 (2002)","journal-title":"Journal of graph algorithms and applications"},{"key":"3_CR15","doi-asserted-by":"crossref","first-page":"100","DOI":"10.1109\/TSSC.1968.300136","volume":"4","author":"P.E. Hart","year":"1968","unstructured":"Hart, P.E., Nilsson, N.J., Raphael, B.: A formal basis for the heuristic determination of minimum cost paths. IEEE transactions on systems science and cybernetics\u00a04, 100\u2013107 (1968)","journal-title":"IEEE transactions on systems science and cybernetics"},{"key":"3_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1007\/978-3-540-24838-5_20","volume-title":"Experimental and Efficient Algorithms","author":"M. Holzer","year":"2004","unstructured":"Holzer, M., Schulz, F., Willhalm, T.: Combining speed-up techniques for shortest-path computations. In: Ribeiro, C.C., Martins, S.L. (eds.) WEA 2004. LNCS, vol.\u00a03059, pp. 269\u2013284. Springer, Heidelberg (2004)"},{"key":"3_CR17","doi-asserted-by":"crossref","unstructured":"Holzer, M., et al.: Combining speed-up techniques for shortest-path computations. ACM Journal of Experimental Algorithmics (JEA) 10(2.05) (2005\u20132006)","DOI":"10.1145\/1064546.1180616"},{"key":"3_CR18","first-page":"156","volume-title":"Proc. Algorithm Engineering and Experiments (ALENEX\u201906)","author":"M. Holzer","year":"2006","unstructured":"Holzer, M., Schulz, F., Wagner, D.: Engineering multi-level overlay graphs for shortest-path queries. In: Raman, R., Stallmann, M. (eds.) Proc. Algorithm Engineering and Experiments (ALENEX\u201906), pp. 156\u2013170. SIAM, Philadelphia (2006)"},{"key":"3_CR19","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/321992.321993","volume":"24","author":"D.B. Johnson","year":"1977","unstructured":"Johnson, D.B.: Efficient algorithms for shortest paths in sparse networks. Journal of the ACM (JACM)\u00a024, 1\u201313 (1977)","journal-title":"Journal of the ACM (JACM)"},{"key":"3_CR20","doi-asserted-by":"crossref","first-page":"283","DOI":"10.1613\/jair.460","volume":"7","author":"H. Kaindl","year":"1997","unstructured":"Kaindl, H., Kainz, G.: Bidirectional heuristic search reconsidered. Journal of Artificial Intelligence Research\u00a07, 283\u2013317 (1997)","journal-title":"Journal of Artificial Intelligence Research"},{"key":"3_CR21","doi-asserted-by":"crossref","unstructured":"Karypis, G.: METIS: Family of multilevel partitioning algorithms (1995), http:\/\/www-users.cs.umn.edu\/~karypis\/metis\/","DOI":"10.1145\/224170.224229"},{"key":"3_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"126","DOI":"10.1007\/11427186_13","volume-title":"Experimental and Efficient Algorithms","author":"E. K\u00f6hler","year":"2005","unstructured":"K\u00f6hler, E., M\u00f6hring, R.H., Schilling, H.: Acceleration of shortest path computation. In: Nikoletseas, S.E. (ed.) WEA 2005. LNCS, vol.\u00a03503, pp. 126\u2013138. Springer, Heidelberg (2005)"},{"key":"3_CR23","series-title":"IfGI prints","first-page":"219","volume-title":"Geoinformation und Mobilit\u00e4t - von der Forschung zur praktischen Anwendung","author":"U. Lauther","year":"2004","unstructured":"Lauther, U.: An extremely fast, exact algorithm for finding shortest paths in static networks with geographical background. In: Raubal, M., Sliwinski, A., Kuhn, W. (eds.) Geoinformation und Mobilit\u00e4t - von der Forschung zur praktischen Anwendung. IfGI prints, vol.\u00a022, pp. 219\u2013230. Institut f\u00fcr Geoinformatik, M\u00fcnster (2004)"},{"key":"3_CR24","doi-asserted-by":"publisher","first-page":"551","DOI":"10.1007\/BF01553908","volume":"4","author":"M. Luby","year":"1989","unstructured":"Luby, M., Ragde, P.: A bidirectional shortest-path algorithm with good average-case behavior. Algorithmica\u00a04, 551\u2013567 (1989)","journal-title":"Algorithmica"},{"key":"3_CR25","volume-title":"LEDA, A platform for Combinatorial and Geometric Computing","author":"K. Mehlhorn","year":"1999","unstructured":"Mehlhorn, K., N\u00e4her, S.: LEDA, A platform for Combinatorial and Geometric Computing. Cambridge University Press, Cambridge (1999)"},{"key":"3_CR26","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1016\/S0196-6774(03)00046-4","volume":"48","author":"U. Meyer","year":"2003","unstructured":"Meyer, U.: Average-case complexity of single-source shortest-paths algorithms: lower and upper bounds. Journal of Algorithms\u00a048, 91\u2013134 (2003)","journal-title":"Journal of Algorithms"},{"key":"3_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1007\/11427186_18","volume-title":"Experimental and Efficient Algorithms","author":"R.H. M\u00f6hring","year":"2005","unstructured":"M\u00f6hring, R.H., et al.: Partitioning graph to speed up dijkstra\u2019s algorithm. In: Nikoletseas, S.E. (ed.) WEA 2005. LNCS, vol.\u00a03503, pp. 189\u2013202. Springer, Heidelberg (2005), Journal version to appear in ACM Journal on Experimental Algorithmics (JEA) 12 (2006)"},{"key":"3_CR28","series-title":"Lecture Notes in Computer Science","volume-title":"Algorithmic Methods for Railway Optimization","author":"M. M\u00fcller-Hannemann","year":"2007","unstructured":"M\u00fcller-Hannemann, M., et al.: Timetable information: Models and algorithms. In: Geraets, F., et al. (eds.) ATMOS 2004. LNCS, vol.\u00a04359, Springer, Heidelberg (2007)"},{"key":"3_CR29","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1007\/3-540-44688-5_15","volume-title":"Algorithm Engineering","author":"M. M\u00fcller-Hannemann","year":"2001","unstructured":"M\u00fcller-Hannemann, M., Weihe, K.: Pareto shortest paths is often feasible in practice. In: Brodal, G.S., Frigioni, D., Marchetti-Spaccamela, A. (eds.) WAE 2001. LNCS, vol.\u00a02141, pp. 185\u2013197. Springer, Heidelberg (2001)"},{"key":"3_CR30","doi-asserted-by":"crossref","unstructured":"Pohl, I.: Bi-directional and heuristic search in path problems. Technical Report 104, Stanford Linear Accelerator Center, Stanford, California (1969)","DOI":"10.2172\/4785039"},{"key":"3_CR31","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)"},{"key":"3_CR32","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/11841036_71","volume-title":"Algorithms \u2013 ESA 2006","author":"P. Sanders","year":"2006","unstructured":"Sanders, P., Schultes, D.: Engineering Highway hierarchies. In: Azar, Y., Erlebach, T. (eds.) ESA 2006. LNCS, vol.\u00a04168, Springer, Heidelberg (2006)"},{"key":"3_CR33","doi-asserted-by":"crossref","unstructured":"Schulz, F., Wagner, D., Weihe, K.: Dijkstra\u2019s algorithm on-line: An empirical case study from public railroad transport. ACM Journal of Experimental Algorithmics (JEA)\u00a05(12) (2000)","DOI":"10.1145\/351827.384254"},{"key":"3_CR34","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1007\/3-540-45643-0_4","volume-title":"Algorithm Engineering and Experiments","author":"F. Schulz","year":"2002","unstructured":"Schulz, F., Wagner, D., Zaroliagis, C.: Using Multi-Level Graphs for Timetable Information. In: Mount, D.M., Stein, C. (eds.) ALENEX 2002. LNCS, vol.\u00a02409, pp. 43\u201359. Springer, Heidelberg (2002)"},{"key":"3_CR35","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 space. Algorithmica\u00a01, 31\u201348 (1986)","journal-title":"Algorithmica"},{"key":"3_CR36","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"776","DOI":"10.1007\/978-3-540-39658-1_69","volume-title":"Algorithms - ESA 2003","author":"D. Wagner","year":"2003","unstructured":"Wagner, D., Willhalm, T.: Geometric Speed-Up Techniques for Finding Shortest Paths in Large Sparse Graphs. In: Di Battista, G., Zwick, U. (eds.) ESA 2003. LNCS, vol.\u00a02832, pp. 776\u2013787. Springer, Heidelberg (2003)"},{"key":"3_CR37","unstructured":"Wagner, D., Willhalm, T.: Drawing graphs to speed up shortest-path computations. In: Joint Proc. 7th Workshop Algorithm Engineering and Experiments (ALENEX 2005) and 2nd Workshop Analytic Algorithmics and Combinatorics (ANALCO ), pp. 15\u201322 (2005)"},{"key":"3_CR38","doi-asserted-by":"crossref","unstructured":"Wagner, D., Willhalm, T., Zaroliagis, C.: Geometric shortest path containers. ACM Journal on Experimental Algorithmics (JEA)\u00a010(1.03) (2005-2006)","DOI":"10.1145\/1064546.1103378"}],"container-title":["Lecture Notes in Computer Science","STACS 2007"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-70918-3_3.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,19]],"date-time":"2020-11-19T05:11:51Z","timestamp":1605762711000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-70918-3_3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540709176","9783540709183"],"references-count":38,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-70918-3_3","relation":{},"subject":[]}}