Quick links

Highway Dimension and Provably Efficient Shortest Path Algorithms

Date and Time
Wednesday, October 14, 2009 - 4:30pm to 5:30pm
Computer Science Small Auditorium (Room 105)
CS Department Colloquium Series
Andrew Goldberg, from Microsoft Research - Silicon Valley
Robert Tarjan
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.

Joint work with Ittai Abraham, Amos Fiat, and Renato Werneck

Follow us: Facebook Twitter Linkedin