Distances and shortest paths on graphs of bounded highway dimension: Simple, Fast, Dynamic

Speaker: John Iacono, Université Libre de Bruxelles and Synapsis Group

Title:   "Distances and shortest paths on graphs of bounded highway
dimension: Simple, Fast, Dynamic"

Date: Thursday, 30 November 2023
Time: 9:30 am - 10:30 am
Venue: Rm3520 (CSE Conference Room, via lift 25/26)

Abstract:

Dijkstra's algorithm is the standard method for computing shortest paths
on arbitrary graphs. However, it is slow for large graphs, taking at least
linear time. It has been long known that for real world road networks,
creating a hierarchy of well-chosen shortcuts allows fast distance and
path computation, with exact distance queries seemingly being answered in
logarithmic time. However, these methods were but heuristics until the
work of Abraham et al.~[JACM 2016], where they defined a graph parameter
called highway dimension which is constant for real-world road networks,
and showed that in graphs of constant highway dimension, a shortcut
hierarchy exists that guarantees shortest distance computation takes
$O(\log (U+|V|))$ time and $O(V \log (U+|V|))$ space, where $U$ is the
ratio of the smallest to largest edge, and $|V|$ is the number of
vertices. The problem is that they were unable to efficiently compute the
hierarchy of shortcuts. Here we present a simple and efficient algorithm
to compute the needed hierarchy of shortcuts in time and space $O(V \log
(U+|V|))$, as well as supporting updates in time $O( \log (U+|V|))$.

Joint work with Sébastien Collette (Synapsis Group)