Home > News > Martin Pečar: Graph augmentation speed-up approaches

Martin Pečar: Graph augmentation speed-up approaches

Date: 26. 2. 2012
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.).