Brief announcement: Sublinear-space distance labeling using hubs

Paweł Gawrychowski, Adrian Kosowski, Przemyslaw Uznanski

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

Abstract

A distance labeling scheme is an assignment of bit-labels to the vertices of an undirected, unweighted graph such that the distance between any pair of vertices can be decoded solely from their labels. We propose a series of new labeling schemes within the framework of so-called hub labeling (HL, also known as landmark labeling or 2-hop-cover labeling), in which each node u stores its distance to all nodes from an appropriately chosen set of hubs S(u) ⊆ V . For a queried pair of nodes (u; v), the length of a shortest u..v-path passing through a hub node from S(u)∩(v) is then used as an upper bound on the distance between u and v. We present a hub labeling which allows us to decode ex- act distances in sparse graphs using labels of size sublinear in the number of nodes. For graphs with at most n nodes and average degree δ, the tradeoff between label bit size L and query decoding time T for our approach is given by L = O(n log logδ T= logδ T), for any T ≤ n. Our simple approach is thus the first sublinear-space distance labeling for sparse graphs that simultaneously admits small decoding time (for constant δ, we can achieve any T = ω(1) while maintaining L = o(n)), and it also provides an improve- ment in terms of label size with respect to previous slower approaches. By using similar techniques, we then present a 2-additive labeling scheme for general graphs, i.e., one in which the decoder provides a 2-additive-approximation of the distance between any pair of nodes. We achieve the same label size- time tradeoff L = O(n log2 log T= log T), for any T ≤ n. To our knowledge, this is the first additive scheme with con- stant absolute error to use labels of sublinear size. The corresponding decoding time is then small (any T = ω(1) is sufficient).

Original languageEnglish
Title of host publicationPODC 2016 - Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing
PublisherACM
Pages43-45
Number of pages3
Volume25-28-July-2016
ISBN (Electronic)9781450339643
DOIs
Publication statusPublished - 25 Jul 2016
MoE publication typeA4 Article in a conference publication
EventACM Symposium on Principles of Distributed Computing - Chicago, United States
Duration: 25 Jul 201628 Jul 2016
Conference number: 35

Conference

ConferenceACM Symposium on Principles of Distributed Computing
Abbreviated titlePODC
CountryUnited States
CityChicago
Period25/07/201628/07/2016

Keywords

  • Algorithms
  • Distance Labeling
  • Distance Oracles
  • Distributed Data Structures
  • Graphs

Fingerprint Dive into the research topics of 'Brief announcement: Sublinear-space distance labeling using hubs'. Together they form a unique fingerprint.

Cite this