|
|
|
Tobias Rupp and Stefan Funke
We prove a Ω(n)" role="presentation">O(??--v)O(n)
O
(
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 fam...
ver más
|
|
|
|
|
|
|
Lars Gottesbüren, Michael Hamann, Tim Niklas Uhl and Dorothea Wagner
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...
ver más
|
|
|
|
|
|
|
Ben Strasser, Dorothea Wagner and Tim Zeitz
We study the problem of quickly computing point-to-point shortest paths in massive road networks with traffic predictions. Incorporating traffic predictions into routing allows, for example, to avoid commuter traffic congestions. Existing techniques foll...
ver más
|
|
|
|