• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site

Book chapter

On the Complexity of Hub Labeling (Extended Abstract)

P. 62-74.
Babenko M. A., Goldberg A., Weller M., Savchenko R., Kaplan H.

Hub Labeling (HL) is a data structure for distance oracles. Hierarchical HL (HHL) is a special type ofHL, that received a lot of attention from a practical point of view. However, theoretical questions such as NP-hardness and approximation guarantees for HHL algorithms have been left aside. We study the computational complexity of HL and HHL. We prove that both HL and HHL are NP-hard, and present upper and lower bounds on the approximation ratios of greedy HHL algorithms that are used in practice. We also introduce a new variant of the greedy HHL algorithm that produces small labels for graphs with small highway dimension.

In book

Edited by: G. Italiano, G. Pighizzini, S. Donald. Vol. 9235. Springer, 2015.