Sublinear distance labeling

TY - GEN

T1 - Sublinear distance labeling

AU - Alstrup, Stephen

AU - Dahlgaard, Søren

AU - Knudsen, Mathias Bæk Tejs

AU - Porat, Ely

N1 - Conference code: 24

PY - 2016/8/1

Y1 - 2016/8/1

N2 - A distance labeling scheme labels the n nodes of a graph with binary strings such that, given the labels of any two nodes, one can determine the distance in the graph between the two nodes by looking only at the labels. A D-preserving distance labeling scheme only returns precise distances between pairs of nodes that are at distance at least D from each other. In this paper we consider distance labeling schemes for the classical case of unweighted and undirected graphs. We present a O(n/D log2 D) bit D-preserving distance labeling scheme, improving the previous bound by Bollobás et al. [SIAM J. Discrete Math. 2005]. We also give an almost matching lower bound of Ω(n/D). With our D-preserving distance labeling scheme as a building block, we additionally achieve the following results: 1. We present the first distance labeling scheme of size o(n) for sparse graphs (and hence bounded degree graphs). This addresses an open problem by Gavoille et al. [J. Algo. 2004], hereby separating the complexity from distance labeling in general graphs which require Ω(n) bits, Moon [Proc. of Glasgow Math. Association 1965].1 For approximate r-additive labeling schemes, that return distances within an additive error of r we show a scheme of size O(n/r · polylog(r log n/log n) for r ≥ 2. This improves on the current best bound of O (n/r) by Alstrup et. al. [SODA 2016] for sub-polynomial r, and is a generalization of a result by Gawrychowski et al. [arXiv preprint 2015] who showed this for r = 2.

AB - A distance labeling scheme labels the n nodes of a graph with binary strings such that, given the labels of any two nodes, one can determine the distance in the graph between the two nodes by looking only at the labels. A D-preserving distance labeling scheme only returns precise distances between pairs of nodes that are at distance at least D from each other. In this paper we consider distance labeling schemes for the classical case of unweighted and undirected graphs. We present a O(n/D log2 D) bit D-preserving distance labeling scheme, improving the previous bound by Bollobás et al. [SIAM J. Discrete Math. 2005]. We also give an almost matching lower bound of Ω(n/D). With our D-preserving distance labeling scheme as a building block, we additionally achieve the following results: 1. We present the first distance labeling scheme of size o(n) for sparse graphs (and hence bounded degree graphs). This addresses an open problem by Gavoille et al. [J. Algo. 2004], hereby separating the complexity from distance labeling in general graphs which require Ω(n) bits, Moon [Proc. of Glasgow Math. Association 1965].1 For approximate r-additive labeling schemes, that return distances within an additive error of r we show a scheme of size O(n/r · polylog(r log n/log n) for r ≥ 2. This improves on the current best bound of O (n/r) by Alstrup et. al. [SODA 2016] for sub-polynomial r, and is a generalization of a result by Gawrychowski et al. [arXiv preprint 2015] who showed this for r = 2.

U2 - 10.4230/LIPIcs.ESA.2016.5

DO - 10.4230/LIPIcs.ESA.2016.5

M3 - Article in proceedings

SN - 978-3-95977-015-6

T3 - Leibniz International Proceedings in Informatics

BT - 24th Annual European Symposium on Algorithms (ESA 2016)

A2 - Sankowski, Piotr

A2 - Zaroliagis, Christos

PB - Schloss Dagstuhl - Leibniz-Zentrum für Informatik

T2 - 24th Annual European Symposium on Algorithms

Y2 - 22 August 2016 through 26 August 2016

ER -