{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,29]],"date-time":"2026-06-29T22:01:26Z","timestamp":1782770486546,"version":"3.54.5"},"reference-count":35,"publisher":"MDPI AG","issue":"9","license":[{"start":{"date-parts":[[2019,9,16]],"date-time":"2019-09-16T00:00:00Z","timestamp":1568592000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["WA654\/19-2"],"award-info":[{"award-number":["WA654\/19-2"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["WA654\/22-2"],"award-info":[{"award-number":["WA654\/22-2"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100009133","name":"Karlsruher Institut f\u00fcr Technologie","doi-asserted-by":"publisher","award":["KIT-Publication Fund"],"award-info":[{"award-number":["KIT-Publication Fund"]}],"id":[{"id":"10.13039\/100009133","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>Graph partitioning has many applications. We consider the acceleration of shortest path queries in road networks using Customizable Contraction Hierarchies (CCH). It is based on computing a nested dissection order by recursively dividing the road network into parts. Recently, with FlowCutter and Inertial Flow, two flow-based graph bipartitioning algorithms have been proposed for road networks. While FlowCutter achieves high-quality results and thus fast query times, it is rather slow. Inertial Flow is particularly fast due to the use of geographical information while still achieving decent query times. We combine the techniques of both algorithms to achieve more than six times faster preprocessing times than FlowCutter and even faster queries on the Europe road network. We show that, using 16 cores of a shared-memory machine, this preprocessing needs four minutes.<\/jats:p>","DOI":"10.3390\/a12090196","type":"journal-article","created":{"date-parts":[[2019,9,17]],"date-time":"2019-09-17T03:31:46Z","timestamp":1568691106000},"page":"196","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":10,"title":["Faster and Better Nested Dissection Orders for Customizable Contraction Hierarchies"],"prefix":"10.3390","volume":"12","author":[{"given":"Lars","family":"Gottesb\u00fcren","sequence":"first","affiliation":[{"name":"Institute of Theoretical Informatics, Karlsruhe Institute of Technology, Am Fasanengarten 5, 76131 Karlsruhe, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Michael","family":"Hamann","sequence":"additional","affiliation":[{"name":"Institute of Theoretical Informatics, Karlsruhe Institute of Technology, Am Fasanengarten 5, 76131 Karlsruhe, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Tim Niklas","family":"Uhl","sequence":"additional","affiliation":[{"name":"Institute of Theoretical Informatics, Karlsruhe Institute of Technology, Am Fasanengarten 5, 76131 Karlsruhe, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Dorothea","family":"Wagner","sequence":"additional","affiliation":[{"name":"Institute of Theoretical Informatics, Karlsruhe Institute of Technology, Am Fasanengarten 5, 76131 Karlsruhe, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"1968","published-online":{"date-parts":[[2019,9,16]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1007\/978-3-319-49487-6_4","article-title":"Recent Advances in Graph Partitioning","volume":"Volume 9220","author":"Kliemann","year":"2016","journal-title":"Algorithm Engineering\u2014Selected Results and Surveys"},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1007\/BF01386390","article-title":"A Note on Two Problems in Connexion with Graphs","volume":"1","author":"Dijkstra","year":"1959","journal-title":"Numer. Math."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1007\/978-3-319-49487-6_2","article-title":"Route Planning in Transportation Networks","volume":"Volume 9220","author":"Kliemann","year":"2016","journal-title":"Algorithm Engineering\u2014Selected Results and Surveys"},{"key":"ref_4","first-page":"1","article-title":"Partitioning Graphs to Speedup Dijkstra\u2019s Algorithm","volume":"11","author":"Schilling","year":"2006","journal-title":"ACM J. Exp. Algorithm."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1090\/dimacs\/074\/03","article-title":"Fast Point-to-Point Shortest Path Computations with Arc-Flags","volume":"Volume 74","author":"Demetrescu","year":"2009","journal-title":"The Shortest Path Problem: Ninth DIMACS Implementation Challenge"},{"key":"ref_6","unstructured":"Munro, I., and Wagner, D. (2008, January 19). SHARC: Fast and Robust Unidirectional Routing. Proceedings of the 10th Workshop on Algorithm Engineering and Experiments (ALENEX\u201908), San Francisco, CA, USA."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/2133803.2330080","article-title":"Engineering Highway Hierarchies","volume":"17","author":"Sanders","year":"2012","journal-title":"ACM J. Exp. Algorithm."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1671970.1671976","article-title":"Combining Hierarchical and Goal-Directed Speed-Up Techniques for Dijkstra\u2019s Algorithm","volume":"15","author":"Bauer","year":"2010","journal-title":"ACM J. Exp. Algorithm."},{"key":"ref_9","unstructured":"Gutman, R.J. (2004, January 10). Reach-Based Routing: A New Approach to Shortest Path Algorithms Optimized for Road Networks. Proceedings of the 6th Workshop on Algorithm Engineering and Experiments (ALENEX\u201904), New Orleans, LA, USA."},{"key":"ref_10","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_11","doi-asserted-by":"crossref","first-page":"566","DOI":"10.1287\/trsc.2014.0579","article-title":"Customizable Route Planning in Road Networks","volume":"51","author":"Delling","year":"2017","journal-title":"Transp. Sci."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/2886843","article-title":"Customizable Contraction Hierarchies","volume":"21","author":"Dibbelt","year":"2016","journal-title":"ACM J. Exp. Algorithm."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"345","DOI":"10.1137\/0710032","article-title":"Nested Dissection of a Regular Finite Element Mesh","volume":"10","author":"George","year":"1973","journal-title":"SIAM J. Numer. Anal."},{"key":"ref_14","first-page":"1","article-title":"Graph Bisection with Pareto Optimization","volume":"23","author":"Hamann","year":"2018","journal-title":"ACM J. Exp. Algorithm."},{"key":"ref_15","unstructured":"Schild, A., and Sommer, C. (July, January 29). On Balanced Separators in Road Networks. Proceedings of the 14th International Symposium on Experimental Algorithms (SEA\u201915), Paris, France. Lecture Notes in Computer Science."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"164","DOI":"10.1007\/978-3-642-38527-8_16","article-title":"Think Locally, Act Globally: Highly Balanced Graph Partitioning","volume":"Volume 7933","author":"Sanders","year":"2013","journal-title":"Proceedings of the 12th International Symposium on Experimental Algorithms (SEA\u201913)"},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"359","DOI":"10.1137\/S1064827595287997","article-title":"A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs","volume":"20","author":"Karypis","year":"1999","journal-title":"SIAM J. Sci. Comput."},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Delling, D., Goldberg, A.V., Razenshteyn, I., and Werneck, R.F. (2011, January 16\u201320). Graph Partitioning with Natural Cuts. Proceedings of the 25th International Parallel and Distributed Processing Symposium (IPDPS\u201911), Anchorage, AK, USA.","DOI":"10.1109\/IPDPS.2011.108"},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Sanders, P., and Schulz, C. (2012, January 16). Distributed Evolutionary Graph Partitioning. Proceedings of the 14th Meeting on Algorithm Engineering and Experiments (ALENEX\u201912), Kyoto, Japan.","DOI":"10.1137\/1.9781611972924.2"},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"399","DOI":"10.4153\/CJM-1956-045-5","article-title":"Maximal flow through a network","volume":"8","author":"Ford","year":"1956","journal-title":"Can. J. Math."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"112","DOI":"10.1016\/j.tcs.2016.07.003","article-title":"Search-space size in contraction hierarchies","volume":"645","author":"Bauer","year":"2016","journal-title":"Theor. Comput. Sci."},{"key":"ref_22","unstructured":"Strasser, B. (2019, May 22). FlowCutter Implementation. Available online: https:\/\/github.com\/kit-algo\/flow-cutter\/tree\/cch-tree-order."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1016\/0020-0190(88)90194-9","article-title":"Optimal Node Ranking of Trees","volume":"28","author":"Iyer","year":"1988","journal-title":"Inf. Process. Lett."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1016\/0020-0190(89)90161-0","article-title":"Optimal node ranking of trees in linear time","volume":"33","year":"1989","journal-title":"Inf. Process. Lett."},{"key":"ref_25","unstructured":"Ahuja, R.K., Magnanti, T.L., and Orlin, J.B. (1993). Network Flows: Theory, Algorithms, and Applications, Prentice Hall."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"372","DOI":"10.1145\/362248.362272","article-title":"Efficient Algorithms for Graph Manipulation","volume":"16","author":"Hopcroft","year":"1973","journal-title":"Commun. ACM"},{"key":"ref_27","doi-asserted-by":"crossref","unstructured":"Demetrescu, C., Goldberg, A.V., and Johnson, D.S. (2009). The Shortest Path Problem: Ninth DIMACS Implementation Challenge, American Mathematical Society. DIMACS Book.","DOI":"10.1090\/dimacs\/074"},{"key":"ref_28","unstructured":"Gottesb\u00fcren, L., Hamann, M., and Uhl, T. (2019, June 28). Available online: https:\/\/github.com\/kit-algo\/InertialFlowCutter."},{"key":"ref_29","unstructured":"Strasser, B. (2019, June 03). CCH Implementation in RoutingKit. Available online: https:\/\/github.com\/RoutingKit\/RoutingKit."},{"key":"ref_30","unstructured":"Buchhold, V., Sanders, P., and Wagner, D. (2018, January 27\u201329). Real-Time Traffic Assignment Using Fast Queries in Customizable Contraction Hierarchies. Proceedings of the 17th International Symposium on Experimental Algorithms (SEA\u201918), L\u2019Aquila, Italy. Leibniz International Proceedings in Informatics."},{"key":"ref_31","unstructured":"Schulz, C. (2019, June 10). KaHiP Implementation. Available online: https:\/\/github.com\/schulzchristian\/KaHIP."},{"key":"ref_32","unstructured":"Karypis, G., and Kumar, V. (2019, June 10). Metis Binary Distribution. Available online: http:\/\/glaros.dtc.umn.edu\/gkhome\/metis\/metis\/download."},{"key":"ref_33","first-page":"1277","article-title":"Algorithm for Solution of a Problem of Maximum Flow in a Network with Power Estimation","volume":"11","author":"Dinitz","year":"1970","journal-title":"Sov. Math.-Dokl."},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"294","DOI":"10.1007\/978-3-319-38851-9_20","article-title":"Advanced Multilevel Node Separator Algorithms","volume":"Volume 9685","author":"Sanders","year":"2016","journal-title":"Proceedings of the 15th International Symposium on Experimental Algorithms (SEA\u201916)"},{"key":"ref_35","doi-asserted-by":"crossref","unstructured":"Schulz, A.S., Skutella, M., Stiller, S., and Wagner, D. (2015). Graph Fill-In, Elimination Ordering, Nested Dissection and Contraction Hierarchies. Gems of Combinatorial Optimization and Graph Algorithms, Springer.","DOI":"10.1007\/978-3-319-24971-1"}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/12\/9\/196\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T13:20:31Z","timestamp":1760188831000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/12\/9\/196"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,9,16]]},"references-count":35,"journal-issue":{"issue":"9","published-online":{"date-parts":[[2019,9]]}},"alternative-id":["a12090196"],"URL":"https:\/\/doi.org\/10.3390\/a12090196","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,9,16]]}}}