Город: Санкт-Петербург Новосибирск Казань Язык: Русский English

Highway Dimension and Provably Efficient Shortest Path Algorithms
Алгоритмы на графах

Что: Лекция
Когда: Воскресенье, 31 января 2010, 13:00–15:00
Слайды: graphalgorithms_lecture_310110.pdf


Computing driving directions has motivated many shortest path heuristics that answer queries on continental scale networks, with tens of millions of intersections, in real time, and with very low storage overhead. We give the first theoretical analysis of several underlying algorithms on a non-trivial class of networks. To do this, we introduce the notion of highway dimension. Our analysis works for networks with low highway dimension and gives a unified explanation of good performance for several seemingly different algorithms.