Beyond Highway Dimension: Small Distance Labels Using Tree Skeletons

Adrian Kosowski 1 Laurent Viennot 1
1 GANG - Networks, Graphs and Algorithms
Inria de Paris, IRIF - Institut de Recherche en Informatique Fondamentale
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 metadatas

Cited literature [27 references]  Display  Hide  Download

https://hal.inria.fr/hal-01359084
Contributor : Adrian Kosowski <>
Submitted on : Saturday, December 10, 2016 - 6:30:24 PM
Last modification on : Friday, January 4, 2019 - 5:33:38 PM
Long-term archiving on : Monday, March 27, 2017 - 11:40:24 PM

Files

paper.pdf
Files produced by the author(s)

Identifiers

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

Collections

Citation

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⟩

Share

Metrics

Record views

489

Files downloads

224