GRASP. Extending Graph Separators for the Single-Source Shortest-Path Problem Full text

Alexandros Efentakis, Dieter Pfoser
22nd Annual European Symposium on Algorithms (ESA 2014)
Περίληψη. Many existing solutions focus on point-to-point shortest-path queries in road networks. In contrast, only few contributions address the related single-source shortest-path problem, i.e., finding shortest-path distances from a single source s to all other graph vertices. This work extends graph separator methods to handle this specific problem and its one-to-many variant, i.e., calculating the shortest path distances from a single source to a set of targets T ⊆ V. This novel family of so-called GRASP algorithms provides exceptional preprocessing times, making them suitable for dynamic travel time scenarios. GRASP algorithms also efficiently solve range / isochrone queries not handled by previous approaches.