# Martin Pečar: Graph augmentation speed-up approaches

Date: 26. 2. 2012

Source: Discrete mathematics seminar

Source: Discrete mathematics seminar

Torek, 28. 2. 2012 od 10h do 12h, Plemljev seminar, Jadranska 19

**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.).