Martin Pečar: Graph augmentation speed-up approaches

Povzetek: Many real-life problems can be solved with graph algorithms. One of the most basic is finding an optimal path in a transportation (e.g. road) network. Classical approach uses Dijkstra or A* algorithm. However, query times may be quite big for a large network, since the computational complexity is O(m log n). Some very interesting speed-up approaches (Highway Hierarchies and similar) have been developed in the last few years, which enable finding exact solution in logarithmic time. To achieve this high performance, graph needs to be preprocessed and augmented with additional information (shortcuts, chosen vertices and distance tables, etc.).