Graph augmentation speed-up approaches (Seminar DM)

Iz MaFiRaWiki

Graph augmentation speed-up approaches

Martin Pečar


Torek, 28. februar 2012, od 10-12, Plemljev seminar, Jadranska 19


Povzetek: Many real-life problems can be solved with graph algorithms. One of the most basic is finding 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.).


Glej tudi/See also


Seminar za diskretno matematiko

Osebna orodja