On the Complexity of Hub Labeling (Extended Abstract)

DOI10.1007/978-3-662-48054-0_6zbMath1465.68054OpenAlexW2178467091MaRDI QIDQ2946377

Ruslan Savchenko, Mathias Weller, Andrew V. Goldberg, Haim Kaplan, Maxim A. Babenko

Publication date: 16 September 2015

Published in: Mathematical Foundations of Computer Science 2015 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-662-48054-0_6

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Data structures (68P05) Approximation algorithms (68W25)

Related Items (4)

Lower Bounds in the Preprocessing and Query Phases of Routing Algorithms ⋮ Eccentricity queries and beyond using hub labels ⋮ On the Complexity of Hub Labeling (Extended Abstract) ⋮ Customizable hub labeling: properties and algorithms

Cites Work

• Unnamed Item
• Unnamed Item
• Separating Hierarchical and General Hub Labelings
• Hierarchical Hub Labelings for Shortest Paths
• Robust Distance Queries on Massive Networks
• On the Complexity of Hub Labeling (Extended Abstract)
• VC-Dimension and Shortest Path Algorithms
• Highway Dimension and Provably Efficient Shortest Path Algorithms
• Reachability and Distance Queries via 2-Hop Labels
• A Fast Parametric Maximum Flow Algorithm and Applications
• Distance labeling in graphs
• Proximity-preserving labeling schemes
• Algorithms for Hub Label Optimization

This page was built for publication: On the Complexity of Hub Labeling (Extended Abstract)