Monday, August 13, 3pm-4:30pm
Wean 7220
Title: Engineering Speed-Up Techniques for Shortest-Path Computations
Prof. Dr. Dorothea Wagner, Universität Karlsruhe, Germany
http://i11www.iti.uni-karlsruhe.de/members/wagner/
Abstract:
During the last years, impressive progress has been achieved in the field of algorithm engineering. One of the showpieces of algorithm engineering is the computation of shortest paths. In recent years, several speed-up techniques for Dijkstra’s shortest-path algorithm have been published that maintain the correctness of the algorithm but reduce its running time significantly for typical instances. They are usually based on a preprocessing that annotates the graph with additional information which can be used to prune or guide the search. Timetable information in public transport and route planning in road networks are traditional application domains for such techniques.
Results on the search space reduction are usually based on extensive experiments, in most cases with road data from US or Europe. However, one problem arising for algorithm engineering in general, and shortest paths in particular is that of data dependency of experimental results.
In this talk, we provide a condensed overview of new developments and extensions of classic results on speed-up techniques for shortest-path. In particular, we introduce a new methodology for evaluating the performance of speed-up techniques.
