{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,24]],"date-time":"2026-04-24T23:13:03Z","timestamp":1777072383533,"version":"3.51.4"},"publisher-location":"Cham","reference-count":23,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783319079585","type":"print"},{"value":"9783319079592","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-319-07959-2_23","type":"book-chapter","created":{"date-parts":[[2014,6,10]],"date-time":"2014-06-10T16:44:25Z","timestamp":1402418665000},"page":"271-282","source":"Crossref","is-referenced-by-count":24,"title":["Customizable Contraction Hierarchies"],"prefix":"10.1007","author":[{"given":"Julian","family":"Dibbelt","sequence":"first","affiliation":[]},{"given":"Ben","family":"Strasser","sequence":"additional","affiliation":[]},{"given":"Dorothea","family":"Wagner","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"23_CR1","unstructured":"Bast, H., Delling, D., Goldberg, A.V., M\u00fcller\u2013Hannemann, M., Pajor, T., Sanders, P., Wagner, D., Werneck, R.F.: Route planning in transportation networks. In: Technical Report MSR-TR-2014-4. Microsoft Research, Mountain View (2014)"},{"key":"23_CR2","first-page":"1","volume":"18","author":"G.V. Batz","year":"2013","unstructured":"Batz, G.V., Geisberger, R., Sanders, P., Vetter, C.: Minimum time-dependent travel times with contraction hierarchies. ACM J. Exp. Algorithmics\u00a018, 1\u201343 (2013)","journal-title":"ACM J. Exp. Algorithmics"},{"key":"23_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1007\/978-3-642-39206-1_9","volume-title":"Automata, Languages, and Programming","author":"R. Bauer","year":"2013","unstructured":"Bauer, R., Columbus, T., Rutter, I., Wagner, D.: Search-space size in contraction hierarchies. In: Fomin, F.V., Freivalds, R., Kwiatkowska, M., Peleg, D. (eds.) ICALP 2013, Part I. LNCS, vol.\u00a07965, pp. 93\u2013104. Springer, Heidelberg (2013)"},{"key":"23_CR4","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1016\/j.ic.2009.03.008","volume":"208","author":"H.L. Bodlaender","year":"2010","unstructured":"Bodlaender, H.L., Koster, A.M.C.A.: Treewidth computations I. Upper bounds. Inform. and Comput.\u00a0208, 259\u2013275 (2010)","journal-title":"Inform. and Comput."},{"key":"23_CR5","doi-asserted-by":"publisher","first-page":"212","DOI":"10.1007\/s004530010016","volume":"27","author":"S. Chaudhuri","year":"2000","unstructured":"Chaudhuri, S., Zaroliagis, C.: Shortest paths in digraphs of small treewidth. Part I: Sequential algorithms. Algorithmica\u00a027, 212\u2013226 (2000)","journal-title":"Algorithmica"},{"key":"23_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"376","DOI":"10.1007\/978-3-642-20662-7_32","volume-title":"Experimental Algorithms","author":"D. Delling","year":"2011","unstructured":"Delling, D., Goldberg, A.V., Pajor, T., Werneck, R.F.: Customizable route planning. In: Pardalos, P.M., Rebennack, S. (eds.) SEA 2011. LNCS, vol.\u00a06630, pp. 376\u2013387. Springer, Heidelberg (2011)"},{"key":"23_CR7","doi-asserted-by":"publisher","first-page":"1135","DOI":"10.1109\/IPDPS.2011.108","volume-title":"2011 IEEE International Parallel & Distributed Processing Symposium (IPDPS 2011)","author":"D. Delling","year":"2011","unstructured":"Delling, D., Goldberg, A.V., Razenshteyn, I., Werneck, R.F.: Graph partitioning with natural cuts. In: 2011 IEEE International Parallel & Distributed Processing Symposium (IPDPS 2011), pp. 1135\u20131146. IEEE Computer Society, Los Alamitos (2011)"},{"key":"23_CR8","first-page":"30","volume-title":"ALENEX 2012","author":"D. Delling","year":"2012","unstructured":"Delling, D., Goldberg, A.V., Razenshteyn, I., Werneck, R.F.: Exact combinatorial branch-and-bound for graph bisection. In: Bader, D.A., Mutzel, P. (eds.) ALENEX 2012, pp. 30\u201344. SIAM, Philadelphia (2012)"},{"key":"23_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"30","DOI":"10.1007\/978-3-642-38527-8_5","volume-title":"Experimental Algorithms","author":"D. Delling","year":"2013","unstructured":"Delling, D., Werneck, R.F.: Faster customization of road networks. In: Bonifaci, V., Demetrescu, C., Marchetti-Spaccamela, A. (eds.) SEA 2013. LNCS, vol.\u00a07933, pp. 30\u201342. Springer, Heidelberg (2013)"},{"key":"23_CR10","volume-title":"The Shortest Path Problem: Ninth DIMACS Implementation Challenge","year":"2009","unstructured":"Demetrescu, C., Goldberg, A.V., Johnson, D.S. (eds.): The Shortest Path Problem: Ninth DIMACS Implementation Challenge. American Mathematical Society, Rhode Island (2009)"},{"key":"23_CR11","doi-asserted-by":"publisher","first-page":"835","DOI":"10.2140\/pjm.1965.15.835","volume":"15","author":"D.R. Fulkerson","year":"1965","unstructured":"Fulkerson, D.R., Gross, O.A.: Incidence matrices and interval graphs. Pacific J. Math.\u00a015, 835\u2013855 (1965)","journal-title":"Pacific J. Math."},{"key":"23_CR12","doi-asserted-by":"publisher","first-page":"388","DOI":"10.1287\/trsc.1110.0401","volume":"46","author":"R. Geisberger","year":"2012","unstructured":"Geisberger, R., Sanders, P., Schultes, D., Vetter, C.: Exact routing in large road networks using contraction hierarchies. Transportation Science\u00a046, 388\u2013404 (2012)","journal-title":"Transportation Science"},{"key":"23_CR13","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1137\/0710032","volume":"10","author":"A. George","year":"1973","unstructured":"George, A.: Nested dissection of a regular finite element mesh. SIAM J. Numer. Anal.\u00a010, 345\u2013363 (1973)","journal-title":"SIAM J. Numer. Anal."},{"key":"23_CR14","first-page":"154","volume-title":"Sparse Matrix Proceedings","author":"A. George","year":"1978","unstructured":"George, A., Liu, J.W.: A quotient graph model for symmetric factorization. In: Duff, I.S., Stewart, G.W. (eds.) Sparse Matrix Proceedings, pp. 154\u2013175. SIAM, Philadelphia (1978)"},{"key":"23_CR15","first-page":"1","volume":"13","author":"M. Holzer","year":"2008","unstructured":"Holzer, M., Schulz, F., Wagner, D.: Engineering multilevel overlay graphs for shortest-path queries. ACM J. Exp. Algorithmics\u00a013, 1\u201326 (2008)","journal-title":"ACM J. Exp. Algorithmics"},{"key":"23_CR16","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1137\/S1064827595287997","volume":"20","author":"G. Karypis","year":"1999","unstructured":"Karypis, G., Kumar, V.: A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM J. Sci. Comput.\u00a020, 359\u2013392 (1999)","journal-title":"SIAM J. Sci. Comput."},{"key":"23_CR17","doi-asserted-by":"publisher","first-page":"346","DOI":"10.1137\/0716027","volume":"16","author":"R.J. Lipton","year":"1979","unstructured":"Lipton, R.J., Rose, D.J., Tarjan, R.: Generalized nested dissection. SIAM J. Numer. Anal.\u00a016, 346\u2013358 (1979)","journal-title":"SIAM J. Numer. Anal."},{"key":"23_CR18","doi-asserted-by":"crossref","first-page":"353","DOI":"10.1613\/jair.3509","volume":"43","author":"L. Planken","year":"2012","unstructured":"Planken, L., de Weerdt, M., van Krogt, R.: Computing all-pairs shortest paths by leveraging low treewidth. J. Artificial Intelligence Res.\u00a043, 353\u2013388 (2012)","journal-title":"J. Artificial Intelligence Res."},{"key":"23_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"164","DOI":"10.1007\/978-3-642-38527-8_16","volume-title":"Experimental Algorithms","author":"P. Sanders","year":"2013","unstructured":"Sanders, P., Schulz, C.: Think locally, act globally: Highly balanced graph partitioning. In: Bonifaci, V., Demetrescu, C., Marchetti-Spaccamela, A. (eds.) SEA 2013. LNCS, vol.\u00a07933, pp. 164\u2013175. Springer, Heidelberg (2013)"},{"key":"23_CR20","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/351827.351829","volume":"5","author":"F. Schulz","year":"2000","unstructured":"Schulz, F., Wagner, D., Weihe, K.: Dijkstra\u2019s algorithm on-line: An empirical case study from public railroad transport. ACM J. Exp. Algorithmics\u00a05, 1\u201323 (2000)","journal-title":"ACM J. Exp. Algorithmics"},{"key":"23_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"236","DOI":"10.1007\/978-3-642-40942-4_21","volume-title":"KI 2013: Advances in Artificial Intelligence","author":"S. Storandt","year":"2013","unstructured":"Storandt, S.: Contraction hierarchies on grid graphs. In: Timm, I.J., Thimm, M. (eds.) KI 2013. LNCS, vol.\u00a08077, pp. 236\u2013247. Springer, Heidelberg (2013)"},{"key":"23_CR22","doi-asserted-by":"crossref","unstructured":"Sturtevant, N.: Benchmarks for grid-based pathfinding. Transactions on Computational Intelligence and AI in Games (2012)","DOI":"10.1109\/TCIAIG.2012.2197681"},{"key":"23_CR23","volume-title":"Weak contraction hierarchies work! Bachelor thesis","author":"T. Zeitz","year":"2013","unstructured":"Zeitz, T.: Weak contraction hierarchies work! Bachelor thesis. KIT, Karlsruhe (2013)"}],"container-title":["Lecture Notes in Computer Science","Experimental Algorithms"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-07959-2_23","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,27]],"date-time":"2019-05-27T01:57:19Z","timestamp":1558922239000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-07959-2_23"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783319079585","9783319079592"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-07959-2_23","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014]]}}}