{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T02:02:32Z","timestamp":1760234552280,"version":"build-2065373602"},"reference-count":18,"publisher":"MDPI AG","issue":"6","license":[{"start":{"date-parts":[[2021,5,25]],"date-time":"2021-05-25T00:00:00Z","timestamp":1621900800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>We prove a \u03a9(n) lower bound on the query time for contraction hierarchies (CH) as well as hub labels, two popular speed-up techniques for shortest path routing. Our construction is based on a graph family not too far from subgraphs that occur in real-world road networks, in particular, it is planar and has a bounded degree. Additionally, we borrow ideas from our lower bound proof to come up with instance-based lower bounds for concrete road network instances of moderate size, reaching up to 96% of an upper bound given by a constructed CH. For a variant of our instance-based schema applied to some special graph classes, we can even show matching upper and lower bounds.<\/jats:p>","DOI":"10.3390\/a14060164","type":"journal-article","created":{"date-parts":[[2021,5,25]],"date-time":"2021-05-25T13:14:21Z","timestamp":1621948461000},"page":"164","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["A Lower Bound for the Query Phase of Contraction Hierarchies and Hub Labels and a Provably Optimal Instance-Based Schema"],"prefix":"10.3390","volume":"14","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7502-7492","authenticated-orcid":false,"given":"Tobias","family":"Rupp","sequence":"first","affiliation":[{"name":"Institut f\u00fcr Formale Methoden der Informatik, Universit\u00e4t Stuttgart, 70174 Stuttgart, Germany"}]},{"given":"Stefan","family":"Funke","sequence":"additional","affiliation":[{"name":"Institut f\u00fcr Formale Methoden der Informatik, Universit\u00e4t Stuttgart, 70174 Stuttgart, Germany"}]}],"member":"1968","published-online":{"date-parts":[[2021,5,25]]},"reference":[{"key":"ref_1","unstructured":"Gutman, R.J. (2004, January 10). Reach-Based Routing: A New Approach to Shortest Path Algorithms Optimized for Road Networks. Proceedings of the Sixth Workshop on Algorithm Engineering and Experiments and the First Workshop on Analytic Algorithmics and Combinatorics, New Orleans, LA, USA."},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Goldberg, A.V., Kaplan, H., and Werneck, R.F. (2006, January 21). Reach for A*: Efficient Point-to-Point Shortest Path Algorithms. Proceedings of the Workshop on Algorithm Engineering and Experiments (ALENEX), Miami, FL, USA.","DOI":"10.1137\/1.9781611972863.13"},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Sanders, P., and Schultes, D. (2012). Engineering highway hierarchies. ACM J. Exp. Algorithmic, 17.","DOI":"10.1145\/2133803.2330080"},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Bauer, R., and Delling, D. (2008, January 19). SHARC: Fast and Robust Unidirectional Routing. Proceedings of the Workshop on Algorithm Engineering and Experiments (ALENEX), San Francisco, CA, USA.","DOI":"10.1137\/1.9781611972887.2"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"388","DOI":"10.1287\/trsc.1110.0401","article-title":"Exact Routing in Large Road Networks Using Contraction Hierarchies","volume":"46","author":"Geisberger","year":"2012","journal-title":"Transp. Sci."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"566","DOI":"10.1126\/science.1137521","article-title":"Fast routing in road networks with transit nodes","volume":"316","author":"Bast","year":"2007","journal-title":"Science"},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Bast, H., Funke, S., Matijevic, D., Sanders, P., and Schultes, D. (2007, January 6). In Transit to Constant Time Shortest-Path Queries in Road Networks. Proceedings of the Workshop on Algorithm Engineering and Experiments (ALENEX), New Orleans, LA, USA.","DOI":"10.1137\/1.9781611972870.5"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"24","DOI":"10.1007\/978-3-642-33090-2_4","article-title":"Hierarchical Hub Labelings for Shortest Paths","volume":"Volume 7501","author":"Abraham","year":"2012","journal-title":"Lecture Notes in Computer Science"},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Abraham, I., Fiat, A., Goldberg, A.V., and Werneck, R.F. (2010, January 17\u201319). Highway Dimension, Shortest Paths, and Provably Efficient Algorithms. Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Austin, TX, USA.","DOI":"10.1137\/1.9781611973075.64"},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Kosowski, A., and Viennot, L. (2017, January 16\u201319). Beyond Highway Dimension: Small Distance Labels Using Tree Skeletons. Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Barcelona, Spain.","DOI":"10.1137\/1.9781611974782.95"},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Blum, J., Funke, S., and Storandt, S. (2018, January 2\u20137). Sublinear Search Spaces for Shortest Path Planning in Grid and Road Networks. Proceedings of the 32nd AAAI Conference on Artificial Intelligence (AAAI), New Orleans, LA, USA.","DOI":"10.1609\/aaai.v32i1.12075"},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Bauer, R., Columbus, T., Rutter, I., and Wagner, D. (2013, January 8\u201312). Search-Space Size in Contraction Hierarchies. Proceedings of the 40th International Colloquium on Automata, Languages, and Programming (ICALP), Riga, Latvia.","DOI":"10.1007\/978-3-642-39206-1_9"},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Funke, S., and Storandt, S. (2015, January 9\u201311). Provable Efficiency of Contraction Hierarchies with Randomized Preprocessing. Proceedings of the 26th International Symposium on Algorithms and Computation (ISAAC), Nagoya, Japan.","DOI":"10.1007\/978-3-662-48971-0_41"},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1137\/0136016","article-title":"A separator theorem for planar graphs","volume":"36","author":"Lipton","year":"1979","journal-title":"SIAM J. Appl. Math."},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"White, C. (2015, January 14\u201316). Lower Bounds in the Preprocessing and Query Phases of Routing Algorithms. Proceedings of the 23rd Annual European Symposium on Algorithms (ESA), Patras, Greece.","DOI":"10.1007\/978-3-662-48350-3_84"},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"Milosavljevi\u0107, N. (2012, January 23\u201325). On optimal preprocessing for contraction hierarchies. Proceedings of the 5th ACM SIGSPATIAL IWCTS, Redondo Beach, CA, USA.","DOI":"10.1145\/2442942.2442949"},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Eisner, J., and Funke, S. (2012, January 16). Transit Nodes-Lower Bounds and Refined Construction. Proceedings of the 14th Workshop on Algorithm Engineering and Experiments (ALENEX), Kyoto, Japan.","DOI":"10.1137\/1.9781611972924.14"},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Rupp, T., and Funke, S. (2020). A lower bound for the query phase of contraction hierarchies and hub labels. International Computer Science Symposium in Russia, Springer.","DOI":"10.1007\/978-3-030-50026-9_26"}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/14\/6\/164\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T06:07:37Z","timestamp":1760162857000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/14\/6\/164"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,5,25]]},"references-count":18,"journal-issue":{"issue":"6","published-online":{"date-parts":[[2021,6]]}},"alternative-id":["a14060164"],"URL":"https:\/\/doi.org\/10.3390\/a14060164","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2021,5,25]]}}}