{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,16]],"date-time":"2026-03-16T15:47:13Z","timestamp":1773676033181,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":27,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540200642","type":"print"},{"value":"9783540396581","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2003]]},"DOI":"10.1007\/978-3-540-39658-1_69","type":"book-chapter","created":{"date-parts":[[2010,7,22]],"date-time":"2010-07-22T23:24:30Z","timestamp":1279841070000},"page":"776-787","source":"Crossref","is-referenced-by-count":54,"title":["Geometric Speed-Up Techniques for Finding Shortest Paths in Large Sparse Graphs"],"prefix":"10.1007","author":[{"given":"Dorothea","family":"Wagner","sequence":"first","affiliation":[]},{"given":"Thomas","family":"Willhalm","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"69_CR1","doi-asserted-by":"crossref","unstructured":"Schulz, F., Wagner, D., Weihe, K.: Dijkstra\u2019s algorithm on-line: An empirical case study from public railroad transport. Journal of Experimental Algorithmics\u00a05 (2000)","DOI":"10.1145\/351827.384254"},{"key":"69_CR2","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":"69_CR3","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":"69_CR4","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":"69_CR5","doi-asserted-by":"crossref","unstructured":"Thorup, M.: Undirected single source shortest path in linear time. In: IEEE Symposium on Foundations of Computer Science, pp. 12\u201321 (1997)","DOI":"10.1109\/SFCS.1997.646088"},{"key":"69_CR6","unstructured":"Meyer, U.: Single-source shortest-paths on arbitrary directed graphs in linear average-case time. In: Symposium on Discrete Algorithms, pp. 797\u2013806 (2001)"},{"key":"69_CR7","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":"69_CR8","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":"69_CR9","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1287\/trsc.32.1.65","volume":"32","author":"F.B. Zahn","year":"1998","unstructured":"Zahn, F.B., Noon, C.E.: Shortest path algorithms: An evaluation using real road networks. Transportation Science\u00a032, 65\u201373 (1998)","journal-title":"Transportation Science"},{"key":"69_CR10","unstructured":"Zahn, 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\u00a04 (2000)"},{"key":"69_CR11","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":"69_CR12","unstructured":"Sikl\u00f3ssy, L., Tulp, E.: Trains, an active time-table searcher. In: Proc. 8th European Conf. Artificial Intelligence, pp. 170\u2013175 (1988)"},{"key":"69_CR13","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":"69_CR14","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":"69_CR15","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":"69_CR16","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":"69_CR17","doi-asserted-by":"publisher","first-page":"1167","DOI":"10.1002\/1097-024X(200009)30:11<1167::AID-SPE337>3.0.CO;2-B","volume":"30","author":"A. Fabri","year":"2000","unstructured":"Fabri, A., Giezeman, G.J., Kettner, L., Schirra, S., Sch\u00f6nherr, S.: On the design of CGAL a computational geometry algorithms library. Softw. \u2013 Pract. Exp.\u00a030, 1167\u20131202 (2000)","journal-title":"Softw. \u2013 Pract. Exp."},{"key":"69_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0038202","volume-title":"New Results and New Trends in Computer Science","author":"E. Welzl","year":"1991","unstructured":"Welzl, E.: Smallest enclosing disks (balls and ellipsoids). In: Maurer, H.A. (ed.) New Results and New Trends in Computer Science. LNCS, vol.\u00a0555. Springer, Heidelberg (1991)"},{"key":"69_CR19","volume-title":"MELECON 1983","author":"G. Toussaint","year":"1983","unstructured":"Toussaint, G.: Solving geometric problems with the rotating calipers. In: Protonotarios, E.N. (ed.) MELECON 1983, NY. IEEE, Los Alamitos (1983); A10.02\/1\u20134"},{"key":"69_CR20","doi-asserted-by":"publisher","first-page":"434","DOI":"10.1145\/220279.220338","volume-title":"Proceedings of the eleventh annual symposium on Computational geometry","author":"C. Schwarz","year":"1995","unstructured":"Schwarz, C., Teich, J., Vainshtein, A., Welzl, E., Evans, B.L.: Minimal enclosing parallelogram with application. In: Proceedings of the eleventh annual symposium on Computational geometry, pp. 434\u2013435. ACM Press, New York (1995)"},{"key":"69_CR21","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":"69_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"501","DOI":"10.1007\/3-540-45848-4_59","volume-title":"Graph Drawing","author":"U. Brandes","year":"2002","unstructured":"Brandes, U., Eiglsperger, M., Herman, I., Himsolt, M., Scott, M.: GraphML progress report. In: Mutzel, P., J\u00fcnger, M., Leipert, S. (eds.) GD 2001. LNCS, vol.\u00a02265, pp. 501\u2013512. Springer, Heidelberg (2002)"},{"key":"69_CR23","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":"69_CR24","doi-asserted-by":"crossref","unstructured":"Shekhar, S., Kohli, A., Coyle, M.: Path computation algorithms for advanced traveler information system (atis). In: Proc. 9th IEEE Intl. Conf. Data Eng., pp. 31\u201339 (1993)","DOI":"10.1109\/ICDE.1993.344080"},{"key":"69_CR25","doi-asserted-by":"crossref","unstructured":"Jacob, R., Marathe, M., Nagel, K.: A computational study of routing algorithms for realistic transportation networks. In: Mehlhorn, K., ed.: In: WAE 1998 (1998)","DOI":"10.1145\/347792.347814"},{"key":"69_CR26","series-title":"Machine Intelligence","first-page":"137","volume-title":"Sixth Annual Machine Intelligence Workshop","author":"I. Pohl","year":"1971","unstructured":"Pohl, I.: Bi-directional search. In: Meltzer, B., Michie, D. (eds.) Sixth Annual Machine Intelligence Workshop. Machine Intelligence, vol.\u00a06, pp. 137\u2013140. Edinburgh University Press, Edinburgh (1971)"},{"key":"69_CR27","unstructured":"Jung, S., Pramanik, S.: Hiti graph model of topographical road maps in navigation systems. In: Proc. 12th IEEE Int. Conf. Data Eng., pp. 76\u201384 (1996)"}],"container-title":["Lecture Notes in Computer Science","Algorithms - ESA 2003"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-39658-1_69","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,31]],"date-time":"2019-05-31T13:00:31Z","timestamp":1559307631000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-39658-1_69"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003]]},"ISBN":["9783540200642","9783540396581"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-39658-1_69","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2003]]}}}