{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,17]],"date-time":"2025-10-17T13:36:59Z","timestamp":1760708219234},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540259206"},{"type":"electronic","value":"9783540320784"}],"license":[{"start":{"date-parts":[[2005,1,1]],"date-time":"2005-01-01T00:00:00Z","timestamp":1104537600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005]]},"DOI":"10.1007\/11427186_18","type":"book-chapter","created":{"date-parts":[[2010,7,13]],"date-time":"2010-07-13T17:38:24Z","timestamp":1279042704000},"page":"189-202","source":"Crossref","is-referenced-by-count":42,"title":["Partitioning Graphs to Speed Up Dijkstra\u2019s Algorithm"],"prefix":"10.1007","author":[{"given":"Rolf H.","family":"M\u00f6hring","sequence":"first","affiliation":[]},{"given":"Heiko","family":"Schilling","sequence":"additional","affiliation":[]},{"given":"Birk","family":"Sch\u00fctz","sequence":"additional","affiliation":[]},{"given":"Dorothea","family":"Wagner","sequence":"additional","affiliation":[]},{"given":"Thomas","family":"Willhalm","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"18_CR1","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":"18_CR2","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":"18_CR3","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\u00a05 (2000)","DOI":"10.1145\/351827.384254"},{"key":"18_CR4","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":"18_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","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 and constrained shortest path computation. In: Nikoletseas, S.E. (ed.) WEA 2005. LNCS, vol.\u00a03503, pp. 126\u2013138. Springer, Heidelberg (2005) (submitted to WEA 2005)"},{"key":"18_CR6","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":"18_CR7","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":"18_CR8","volume-title":"Introduction to Algorithms","author":"T.H. Cormen","year":"2001","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms. The MIT Press, Cambridge Massachusetts (2001)"},{"key":"18_CR9","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1137\/S1064827595287997","volume":"20","author":"G. Karypis","year":"1998","unstructured":"Karypis, G., Kumar, V.: A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM Journal on Scientific Computing archive\u00a020, 359\u2013392 (1998)","journal-title":"SIAM Journal on Scientific Computing archive"},{"key":"18_CR10","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":"18_CR11","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)"},{"key":"18_CR12","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":"18_CR13","unstructured":"Goldberg, A.V., Harrelson, C.: Computing the shortest path: a * search meets graph theory. Technical Report MSR-TR-2004-24, Microsoft Research (2003), Accepted at SODA (2005)"},{"key":"18_CR14","first-page":"100","volume-title":"Proc. Algorithm Engineering and Experiments (ALENEX 2004)","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 2004), pp. 100\u2013111. SIAM, Philadelphia (2004)"},{"key":"18_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","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":"18_CR16","unstructured":"Wagner, D., Willhalm, T.: Drawing graphs to speed up shortest-path computations. In: Proc. 7th Workshop Algorithm Engineering and Experiments (ALENEX 2005). LNCS (2005) (to appear)"}],"container-title":["Lecture Notes in Computer Science","Experimental and Efficient Algorithms"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11427186_18","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,10,31]],"date-time":"2021-10-31T06:30:58Z","timestamp":1635661858000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11427186_18"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005]]},"ISBN":["9783540259206","9783540320784"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/11427186_18","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2005]]}}}