Doing More for Less -- Cache-Aware Parallel Contraction Hierarchies Preprocessing

Dennis Luxen, Dennis Schieferdecker

Contraction Hierarchies is a successful speedup-technique to Dijkstra's seminal shortest path algorithm that has a convenient trade-off between preprocessing and query times. We in…