{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,30]],"date-time":"2025-05-30T10:10:02Z","timestamp":1748599802123,"version":"3.41.0"},"publisher-location":"Berlin, Heidelberg","reference-count":12,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662483497"},{"type":"electronic","value":"9783662483503"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-662-48350-3_84","type":"book-chapter","created":{"date-parts":[[2015,9,1]],"date-time":"2015-09-01T01:40:34Z","timestamp":1441071634000},"page":"1013-1024","source":"Crossref","is-referenced-by-count":4,"title":["Lower Bounds in the Preprocessing and Query Phases of Routing Algorithms"],"prefix":"10.1007","author":[{"given":"Colin","family":"White","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,11,12]]},"reference":[{"key":"84_CR1","unstructured":"Abraham, I., Delling, D., Fiat, A., Goldberg, A.V., Werneck, R.F.: Highway dimension and provably efficient shortest path algorithms. Technical Report MSR-TR-2013-91, Microsoft Research (2013)"},{"key":"84_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"230","DOI":"10.1007\/978-3-642-20662-7_20","volume-title":"Experimental Algorithms","author":"I. Abraham","year":"2011","unstructured":"Abraham, I., Delling, D., Goldberg, A.V., Werneck, R.F.: A hub-based labeling algorithm for shortest paths on road networks. In: Pardalos, P.M., Rebennack, S. (eds.) SEA 2011. LNCS, vol.\u00a06630, pp. 230\u2013241. Springer, Heidelberg (2011)"},{"key":"84_CR3","doi-asserted-by":"crossref","unstructured":"Abraham, I., Fiat, A., Goldberg, A.V., Werneck, R.F.: Highway dimension, shortest paths, and provably efficient algorithms. In: Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2010), pp. 782\u2013793. SIAM (2010)","DOI":"10.1137\/1.9781611973075.64"},{"key":"84_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1007\/978-3-642-38527-8_7","volume-title":"Experimental Algorithms","author":"J. Arz","year":"2013","unstructured":"Arz, J., Luxen, D., Sanders, P.: Transit node routing reconsidered. In: Bonifaci, V., Demetrescu, C., Marchetti-Spaccamela, A. (eds.) SEA 2013. LNCS, vol.\u00a07933, pp. 55\u201366. Springer, Heidelberg (2013)"},{"key":"84_CR5","doi-asserted-by":"crossref","unstructured":"Babenko, M.A., Goldberg, A.V., Kaplan, H., Savchenko, R., Weller, M.: On the complexity of hub labeling. CoRR, abs\/1501.02492 (2015)","DOI":"10.1007\/978-3-662-48054-0_6"},{"key":"84_CR6","unstructured":"Bast, H., Delling, D., Goldberg, A., M\u00fcller-Hannemann, M., Pajor, T., Sanders, P., Wagner, D., Werneck, R.: Route planning in transportation networks. Technical report, Microsoft Research (2014)"},{"key":"84_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1007\/978-3-642-13073-1_32","volume-title":"Algorithms and Complexity","author":"R. Bauer","year":"2010","unstructured":"Bauer, R., Columbus, T., Katz, B., Krug, M., Wagner, D.: Preprocessing speed-up techniques is hard. In: Calamoneri, T., Diaz, J. (eds.) CIAC 2010. LNCS, vol.\u00a06078, pp. 359\u2013370. Springer, Heidelberg (2010)"},{"issue":"5","key":"84_CR8","doi-asserted-by":"publisher","first-page":"1338","DOI":"10.1137\/S0097539702403098","volume":"32","author":"E. Cohen","year":"2003","unstructured":"Cohen, E., Halperin, E., Kaplan, H., Zwick, U.: Reachability and distance queries via 2-hop labels. SIAM Journal on Computing\u00a032(5), 1338\u20131355 (2003)","journal-title":"SIAM Journal on Computing"},{"key":"84_CR9","doi-asserted-by":"crossref","unstructured":"Eppstein, D., Goodrich, M.T.: Studying (non-planar) road networks through an algorithmic lens. In: Proceedings of the 16th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (GIS 2008), pp. 1\u201310. ACM Press (2008)","DOI":"10.1145\/1463434.1463455"},{"key":"84_CR10","first-page":"210","volume-title":"Proceedings of the Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2001","author":"C. Gavoille","year":"2001","unstructured":"Gavoille, C., Peleg, D., P\u00e9rennes, S., Raz, R.: Distance labeling in graphs. In: Proceedings of the Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2001, pp. 210\u2013219. Society for Industrial and Applied Mathematics, Philadelphia (2001)"},{"issue":"3","key":"84_CR11","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(3), 388\u2013404 (2012)","journal-title":"Transportation Science"},{"key":"84_CR12","doi-asserted-by":"crossref","unstructured":"Milosavljevi\u0107, N.: On optimal preprocessing for contraction hierarchies. In: Proceedings of the 5th ACM SIGSPATIAL International Workshop on Computational Transportation Science, pp. 33\u201338. ACM Press (2012)","DOI":"10.1145\/2442942.2442949"}],"container-title":["Lecture Notes in Computer Science","Algorithms - ESA 2015"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-48350-3_84","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,30]],"date-time":"2025-05-30T09:57:13Z","timestamp":1748599033000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-48350-3_84"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783662483497","9783662483503"],"references-count":12,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-48350-3_84","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]}}}