Wednesday, 15:45 - 16:10 h, Room: H 3021


Andrew Goldberg
The hub labeling algorithm

Coauthors: Ittai Abraham, Daniel Delling, Amos Fiat, Renato Werneck


The labeling approach to distance oracle design is to precompute a label for every vertex so that distances can be computed from the corresponding labels. This approach has been introduced by [Gavoille et al. '01], who also introduced the Hub Labeling algorithm (HL). HL has been further studied by [Cohen et al. '02].
We study HL in the context of graphs with small highway dimension (e.g., road networks). We show that under this assumption HL labels are small and the queries are sublinear. We also give an approximation algorithm for computing small HL labels that uses the fact that shortest path set systems have small VC-dimension.
Although polynomial-time, precomputation given by theory is too slow for continental-size road networks. However, heuristics guided by the theory are fast, and compute very small labels. This leads to the fastest currently known practical distance oracles for road networks. HL also has efficient (real-time) implementation inside of a relational database (e.g., in SQL).
%Joint work with Ittai Abraham, Daniel Delling, Amos Fiat, and Renato Werneck.


Talk 2 of the invited session Wed.3.H 3021
"Routing in road networks" [...]
Cluster 2
"Combinatorial optimization" [...]


  There are three major facts that should be watched out for in all payday loans in the United States. Of course, the choice is not that easy, as there exist great number of different preparations. Notwithstanding, Cialis is the one that definitely differs from all other products.