{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,30]],"date-time":"2025-10-30T06:59:34Z","timestamp":1761807574239},"publisher-location":"Berlin, Heidelberg","reference-count":27,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540220671"},{"type":"electronic","value":"9783540248385"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2004]]},"DOI":"10.1007\/978-3-540-24838-5_20","type":"book-chapter","created":{"date-parts":[[2010,8,8]],"date-time":"2010-08-08T21:34:14Z","timestamp":1281303254000},"page":"269-284","source":"Crossref","is-referenced-by-count":15,"title":["Combining Speed-Up Techniques for Shortest-Path Computations"],"prefix":"10.1007","author":[{"given":"Martin","family":"Holzer","sequence":"first","affiliation":[]},{"given":"Frank","family":"Schulz","sequence":"additional","affiliation":[]},{"given":"Thomas","family":"Willhalm","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"20_CR1","unstructured":"Zhan, F.B., Noon, C.E.: A comparison between label-setting and label-correcting algorithms for computing one-to-one shortest paths. Journal of Geographic Information and Decision Analysis 4 (2000)"},{"key":"20_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"126","DOI":"10.1007\/3-540-45749-6_15","volume-title":"Algorithms - ESA 2002","author":"C. Barrett","year":"2002","unstructured":"Barrett, C., Bisset, K., Jacob, R., Konjevod, G., Marathe, M.: Classical and contemporary shortest path problems in road networks: Implementation and experimental analysis of the TRANSIMS router. In: M\u00f6hring, R.H., Raman, R. (eds.) ESA 2002. LNCS, vol.\u00a02461, pp. 126\u2013138. Springer, Heidelberg (2002)"},{"key":"20_CR3","doi-asserted-by":"publisher","first-page":"154","DOI":"10.1016\/0377-2217(94)E0349-G","volume":"83","author":"K. Nachtigall","year":"1995","unstructured":"Nachtigall, K.: Time depending shortest-path problems with applications to railway networks. European Journal of Operational Research\u00a083, 154\u2013166 (1995)","journal-title":"European Journal of Operational Research"},{"key":"20_CR4","unstructured":"Preuss, T., Syrbe, J.H.: An integrated traffic information system. In: Proc. 6th Int. Conf. Appl. Computer Networking in Architecture, Construction, Design, Civil Eng. and Urban Planning, europIA 1997 (1997)"},{"key":"20_CR5","doi-asserted-by":"crossref","unstructured":"Shekhar, S., Fetterer, A., Goyal, B.: Materialization trade-offs in hierarchical shortest path algorithms. In: Proc. Symp. on Large Spatial Databases, pp. 94\u2013111 (1997)","DOI":"10.1007\/3-540-63238-7_26"},{"key":"20_CR6","doi-asserted-by":"publisher","first-page":"809","DOI":"10.1137\/S0097539798337716","volume":"30","author":"C. Barrett","year":"2000","unstructured":"Barrett, C., Jacob, R., Marathe, M.: Formal-language-constrained path problems. SIAM Journal on Computing\u00a030, 809\u2013837 (2000)","journal-title":"SIAM Journal on Computing"},{"key":"20_CR7","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":"20_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\u00a034, 596\u2013615 (1987)","journal-title":"Journal of the ACM"},{"key":"20_CR9","first-page":"129","volume":"73","author":"B.V. Cherkassky","year":"1996","unstructured":"Cherkassky, B.V., Goldberg, A.V., Radzik, T.: Shortest paths algorithms: Theory and experimental evaluation. Mathematical Programming\u00a073, 129\u2013174 (1996)","journal-title":"Mathematical Programming"},{"key":"20_CR10","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)"},{"key":"20_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"230","DOI":"10.1007\/3-540-44676-1_19","volume-title":"Algorithms - ESA 2001","author":"A.V. Goldberg","year":"2001","unstructured":"Goldberg, A.V.: A simple shortest path algorithm with linear average time. In: Meyer auf der Heide, F. (ed.) ESA 2001. LNCS, vol.\u00a02161, pp. 230\u2013241. Springer, Heidelberg (2001)"},{"key":"20_CR12","unstructured":"Meyer, U.: Single-source shortest-paths on arbitrary directed graphs in linear average-case time. In: Proc. 12th Symp. on Discrete Algorithms, pp. 797\u2013806 (2001)"},{"key":"20_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"126","DOI":"10.1007\/3-540-45643-0_10","volume-title":"Algorithm Engineering and Experiments","author":"S. Pettie","year":"2002","unstructured":"Pettie, S., Ramachandran, V., Sridhar, S.: Experimental evaluation of a new shortest path algorithm. In: Mount, D.M., Stein, C. (eds.) ALENEX 2002. LNCS, vol.\u00a02409, pp. 126\u2013142. Springer, Heidelberg (2002)"},{"key":"20_CR14","doi-asserted-by":"crossref","unstructured":"Hart, P., Nilsson, N.J., Raphael, B.A.: A formal basis for the heuristic determination of minimum cost paths. IEEE Trans. Sys. Sci. Cybernet. 2 (1968)","DOI":"10.1109\/TSSC.1968.300136"},{"key":"20_CR15","doi-asserted-by":"crossref","unstructured":"Shekhar, S., Kohli, A., Coyle, M.: Path computation algorithms for advanced traveler information system (ATIS). In: Proc. 9th IEEE Int. Conf. Data Eng., pp. 31\u201339 (1993)","DOI":"10.1109\/ICDE.1993.344080"},{"key":"20_CR16","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 Exp. Algorithmics 5 (2000)","DOI":"10.1145\/351827.384254"},{"key":"20_CR17","volume-title":"Network Flows","author":"R. Ahuja","year":"1993","unstructured":"Ahuja, R., Magnanti, T., Orlin, J.: Network Flows. Prentice-Hall, Englewood Cliffs (1993)"},{"key":"20_CR18","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":"20_CR19","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":"20_CR20","unstructured":"Holzer, M.: Hierarchical speed-up techniques for shortest-path algorithms. Technical report, Dept. of Informatics, University of Konstanz, Germany (2003), http:\/\/www.ub.uni-konstanz.de\/kops\/volltexte\/2003\/1038\/"},{"key":"20_CR21","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 railway systems. In: Mount, D.M., Stein, C. (eds.) ALENEX 2002. LNCS, vol.\u00a02409, pp. 43\u201359. Springer, Heidelberg (2002)"},{"key":"20_CR22","doi-asserted-by":"publisher","first-page":"1029","DOI":"10.1109\/TKDE.2002.1033772","volume":"14","author":"S. Jung","year":"2002","unstructured":"Jung, S., Pramanik, S.: An efficient path computation model for hierarchically structured topographical road maps. IEEE Transactions on Knowledge and Data Engineering\u00a014, 1029\u20131046 (2002)","journal-title":"IEEE Transactions on Knowledge and Data Engineering"},{"key":"20_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","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":"20_CR24","volume-title":"The LEDA Platform of Combinatorial and Geometric Computing","author":"S. N\u00e4her","year":"1999","unstructured":"N\u00e4her, S., Mehlhorn, K.: The LEDA Platform of Combinatorial and Geometric Computing. Cambridge University Press, Cambridge (1999), http:\/\/www.algorithmicsolutions.com"},{"key":"20_CR25","doi-asserted-by":"crossref","unstructured":"Waxman, B.M.: Routing of multipoint connections. IEEE Journal on Selected Areas in Communications 6 (1988)","DOI":"10.1109\/49.12889"},{"key":"20_CR26","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":"20_CR27","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)"}],"container-title":["Lecture Notes in Computer Science","Experimental and Efficient Algorithms"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-24838-5_20.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,19]],"date-time":"2020-11-19T04:56:51Z","timestamp":1605761811000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-24838-5_20"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004]]},"ISBN":["9783540220671","9783540248385"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-24838-5_20","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2004]]}}}