15. Maintenance of Multi-level Overlay Graphs for Timetable Queries

Francesco Bruera, Serafino Cicerone, Gianlorenzo D'Angelo, Gabriele Di Stefano & Daniele Frigioni
In railways systems the timetable is typically represented as a weighted digraph on which itinerary queries are answered by shortest path algorithms, usually running Dijkstra's algorithm. Due to the continuously growing size of real-world graphs, there is a constant need for faster algorithms and many techniques have been devised to heuristically speed up Dijkstra's algorithm. One of these techniques is the multi-level overlay graph, that has been recently introduced and shown to be experimentally efficient,...