Applying Skeletons to Speed Up the Arc-Flags Routing Algorithm
Ivan Khomutovskiy, Rebekka Dunker, Jessica Dierking, Julian Egbert, Christian Helms, Finn Schöllkopf, Katrin Casel, Philipp Fischbeck, Tobias Friedrich, Davis Isaac, Simon Krogmann, Pascal Lenzner · Society for Industrial and Applied Mathematics eBooks · 2023
The Single-Source Shortest Path problem is classically solved by applying Dijkstra's algorithm. However, the plain version of this algorithm is far too slow for real-world applications such as routing in large road networks. To amend this, many speed-up techniques have been developed that build on the idea of computing auxiliary data in a preprocessing phase, that is used to speed up the queries. One well-known example is the Arc-Flags algorithm that is based on the idea of precomputing edge flags to make the search more goal-directed. To explain the strong practical performance of such speed-up techniques, several graph parameters have been introduced. The skeleton dimension is one such parameter that has already been used to derive runtime bounds for some speed-up techniques. Moreover, it was experimentally shown to be low in real-world road networks.