Sublinear Distance Labeling

DOI10.4230/LIPICS.ESA.2016.5MaRDI QIDQ4606270zbMATH OpenOpenAlexFDO

Authors Stephen Alstrup, Søren Dahlgaard, Mathias Bæk Tejs Knudsen, Ely Porat

Publication date 2 March 2018

Full work available at URL https://arxiv.org/abs/1507.02618

zbMATH Keywords

graph theorysparse graphsdistance labelinggraph labeling schemes

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Data structures (68P05) Distance in graphs (05C12) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

Abstract: 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 graphs with both directed and undirected edges. We present a $O(fracnDlo{g}^{2}D)$ bit $D$-preserving distance labeling scheme, improving the previous bound by Bollob'as et. al. [SIAM J. Discrete Math. 2005]. We also give an almost matching lower bound of $Omega(fracnD)$. 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 $Omega(n)$ bits, Moon [Proc. of Glasgow Math. Association 1965]. 2. For approximate $r$-additive labeling schemes, that return distances within an additive error of $r$ we show a scheme of size $Oleft(fracnrcdotfracoperatornamepolylog(rlogn)lognight)$ for $rge2$. This improves on the current best bound of $Oleft(fracnright)$ 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$.

Recommendations

• Sublinear-space distance labeling using hubs
• Approximate distance labeling schemes
• scientific article; zbMATH DE number 1875437
• Brief announcement: Sublinear-space distance labeling using hubs
• Distance labeling scheme and split decomposition
• A note on exact distance labeling
• scientific article; zbMATH DE number 19192
• Distance labellings of graphs
• Sublinear time algorithms for earth mover's distance
• Distance labeling in graphs (extended abstract)

Cited in

(19)

• Minimum point-overlap labelling*
• Better distance labeling for unweighted planar graphs
• Isometric universal graphs
• Sublinear-space distance labeling using hubs
• Proximity-preserving labeling schemes
• Hardness of exact distance queries in sparse graphs through hub labeling
• Better distance labeling for unweighted planar graphs
• scientific article; zbMATH DE number 2079365 (Why is no real title available?)
• Near-optimal distance emulator for planar graphs
• Implicit representation of relations
• scientific article; zbMATH DE number 7765385 (Why is no real title available?)
• scientific article; zbMATH DE number 7561636 (Why is no real title available?)
• Algorithms and Computation
• Brief announcement: Sublinear-space distance labeling using hubs
• Sparse Distance Preservers and Additive Spanners
• An adjacency labeling scheme based on a decomposition of trees into caterpillars
• Distance Labels with Optimal Local Stretch
• Simpler, faster and shorter labels for distances in graphs
• Approximate distance labeling schemes

This page was built for publication: Sublinear Distance Labeling

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4606270)