Beyond Highway Dimension: Small Distance Labels Using Tree Skeletons

Adrian Kosowski 1 Laurent Viennot 1
1 GANG - Networks, Graphs and Algorithms
IRIF - 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.
Type de document :
Communication dans un congrès
SODA 2017 - 28th ACM-SIAM Symposium on Discrete Algorithms, Jan 2017, Barcelona, Spain. 2017
Liste complète des métadonnées


https://hal.inria.fr/hal-01359084
Contributeur : Adrian Kosowski <>
Soumis le : samedi 10 décembre 2016 - 18:30:24
Dernière modification le : jeudi 15 juin 2017 - 09:08:46
Document(s) archivé(s) le : lundi 27 mars 2017 - 23:40:24

Fichiers

paper.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • 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. 2017. <hal-01359084v2>

Partager

Métriques

Consultations de
la notice

302

Téléchargements du document

57