|Когда:||Воскресенье, 31 января 2010, 13:00–15:00|
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.