KIT | KIT-Bibliothek | Impressum | Datenschutz

Faster and better nested dissection orders for Customizable Contraction Hierarchies

Gottesbüren, Lars 1; Hamann, Michael 1; Uhl, Tim Niklas ORCID iD icon 1; Wagner, Dorothea 1
1 Institut für Theoretische Informatik (ITI), Karlsruher Institut für Technologie (KIT)


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.

Verlagsausgabe §
DOI: 10.5445/IR/1000100020
Veröffentlicht am 19.11.2019
DOI: 10.3390/a12090196
Zitationen: 14
Zitationen: 8
Cover der Publikation
Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Zeitschriftenaufsatz
Publikationsjahr 2019
Sprache Englisch
Identifikator ISSN: 1999-4893
KITopen-ID: 1000100020
Erschienen in Algorithms
Verlag MDPI
Band 12
Heft 9
Seiten Art.-Nr.: 196
Schlagwörter graph partitioning; nested dissection; route planning; customizable contraction hierarchies
Nachgewiesen in Scopus
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page