MyJournals Home  

RSS FeedsAlgorithms, Vol. 12, Pages 196: Faster and Better Nested Dissection Orders for Customizable Contraction Hierarchies (Algorithms)

 
 

16 september 2019 15:00:12

 
Algorithms, Vol. 12, Pages 196: Faster and Better Nested Dissection Orders for Customizable Contraction Hierarchies (Algorithms)
 


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.


 
229 viewsCategory: Informatics
 
Algorithms, Vol. 12, Pages 194: Unsteady State Lightweight Iris Certification Based on Multi-Algorithm Parallel Integration (Algorithms)
Algorithms, Vol. 12, Pages 195: An Intelligent Artificial Neural Network Modeling of a Magnetorheological Elastomer Isolator (Algorithms)
 
 
blog comments powered by Disqus


MyJournals.org
The latest issues of all your favorite science journals on one page

Username:
Password:

Register | Retrieve

Search:

Informatics


Copyright © 2008 - 2024 Indigonet Services B.V.. Contact: Tim Hulsen. Read here our privacy notice.
Other websites of Indigonet Services B.V.: Nieuws Vacatures News Tweets Nachrichten