Research Training Group 1194 "Self-organizing Sensor-Actuator-Networks"

Combining Hierarchical and Goal-Directed Speed-Up Techniques for Dijkstra’s Algorithm

  • Date:

    March 2010

  • Author:

    R. Bauer, D. Delling, P. Sanders, D. Schieferdecker, D. Schultes, D. Wagner

  • Abstract

    In recent years, highly effective hierarchical and goal-directed speedup techniques for routing in large road networks have been developed. This paper makes a systematic study of combinations of such techniques. These combinations turn out to give the best results in many scenarios, including graphs for unit disk graphs, grid networks, and time-expanded timetables. Besides these quantitative results, we obtain general insights for successful combinations.

  • In:

    ACM Journal of Experimental Algorithmics

  • Publisher:

    ACM

  • Year:

    2010

  • Links: