Andrew V. Goldberg
The Hub Labeling (HL) algorithm takes a graph and a length function as an input, precomputes vertex labels, and uses the labels to implement a distance oracle. The algorithm got a lot of attention recently, both from theoretical and practical points of view. For example, HL leads to the fastest distance oracle implementation for road networks. In this talk we review some theoretical and structural results on HL and outline a robust and scalable implementation of the algorithm. The algorithm scales to road and some social and computer networks with tens of millions of arcs, and supports real-time queries.
Joint work with Daniel Delling, Thomas Pajor, and Renato Werneck