Skip to Main content Skip to Navigation
Conference papers

Beyond Highway Dimension: Small Distance Labels Using Tree Skeletons

Adrian Kosowski 1 Laurent Viennot 1
1 GANG - Networks, Graphs and Algorithms
IRIF (UMR_8243) - Institut de Recherche en Informatique Fondamentale, Inria de Paris
Abstract : The goal of a hub-based distance labeling scheme for a network G = (V, E) is to assign a small subset S(u) ⊆ V to each node u ∈ V, in such a way that for any pair of nodes u, v, the intersection of hub sets S(u) ∩ S(v) contains a node on the shortest uv-path. The existence of small hub sets, and consequently efficient shortest path processing algorithms, for road networks is an empirical observation. A theoretical explanation for this phenomenon was proposed by Abraham et al. (SODA 2010) through a network parameter they called highway dimension, which captures the size of a hitting set for a collection of shortest paths of length at least r intersecting a given ball of radius 2r. In this work, we revisit this explanation, introducing a more tractable (and directly comparable) parameter based solely on the structure of shortest-path spanning trees, which we call skeleton dimension. We show that skeleton dimension admits an intuitive definition for both directed and undirected graphs, provides a way of computing labels more efficiently than by using highway dimension, and leads to comparable or stronger theoretical bounds on hub set size.
Complete list of metadata

Cited literature [27 references]  Display  Hide  Download
Contributor : Adrian Kosowski Connect in order to contact the contributor
Submitted on : Saturday, December 10, 2016 - 6:30:24 PM
Last modification on : Tuesday, January 11, 2022 - 11:16:04 AM
Long-term archiving on: : Monday, March 27, 2017 - 11:40:24 PM


Files produced by the author(s)


  • HAL Id : hal-01359084, version 2
  • ARXIV : 1609.00512


Adrian Kosowski, Laurent Viennot. Beyond Highway Dimension: Small Distance Labels Using Tree Skeletons. SODA 2017 - 28th ACM-SIAM Symposium on Discrete Algorithms, Jan 2017, Barcelona, Spain. ⟨hal-01359084v2⟩



Les métriques sont temporairement indisponibles