Distance labeling schemes for trees

DOI10.4230/LIPICS.ICALP.2016.132MaRDI QIDQ4598274zbMATH OpenOpenAlexFDO

Authors Stephen Alstrup, Inge Li Gørtz, Esben Bistrup Halvorsen, Ely Porat

Publication date 19 December 2017

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

zbMATH Keywords

distance labelingdistributed computinggraph theoryroutingtrees

Mathematics Subject Classification ID

Trees (05C05) Distance in graphs (05C12) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Data structures (68P05) Graph theory (including graph drawing) in computer science (68R10)

Abstract: We consider distance labeling schemes for trees: given a tree with $n$ nodes, label the nodes with binary strings such that, given the labels of any two nodes, one can determine, by looking only at the labels, the distance in the tree between the two nodes. A lower bound by Gavoille et. al. (J. Alg. 2004) and an upper bound by Peleg (J. Graph Theory 2000) establish that labels must use $Theta(lo{g}^{2}n)$ bitsfootnote{Throughout this paper we use $log$ for $lo{g}_2$.}. Gavoille et. al. (ESA 2001) show that for very small approximate stretch, labels use $Theta(lognloglogn)$ bits. Several other papers investigate various variants such as, for example, small distances in trees (Alstrup et. al., SODA'03). We improve the known upper and lower bounds of exact distance labeling by showing that $frac14lo{g}^{2}n$ bits are needed and that $frac12lo{g}^{2}n$ bits are sufficient. We also give ($1+epsilon$)-stretch labeling schemes using $Theta(logn)$ bits for constant $epsilon>0$. ($1+epsilon$)-stretch labeling schemes with polylogarithmic label size have previously been established for doubling dimension graphs by Talwar (STOC 2004). In addition, we present matching upper and lower bounds for distance labeling for caterpillars, showing that labels must have size $2logn-Theta(loglogn)$. For simple paths with $k$ nodes and edge weights in $[1,n]$, we show that labels must have size $frack-1klogn+Theta(logk)$.

Recommendations

• scientific article; zbMATH DE number 2079400
• Labeling Schemes for Small Distances in Trees
• Optimal distance labeling schemes for trees
• Distance labeling in graphs
• Distance labeling in graphs (extended abstract)

Cited in

(20)

• Distance and routing labeling schemes for cube-free median graphs
• Labeling schemes for weighted dynamic trees
• Informative labeling schemes for graphs
• scientific article; zbMATH DE number 2079400 (Why is no real title available?)
• Distance labeling in graphs
• Isometric universal graphs
• Distance labeling schemes for cube-free median graphs
• Optimal distance labeling schemes for trees
• scientific article; zbMATH DE number 5274833 (Why is no real title available?)
• On local representation of distances in trees
• Application of Bearing and Distance Trees to the Identification of Landmarks on the Coast
• Labeling Schemes for Small Distances in Trees
• Algorithms and Computation
• Better distance labeling for unweighted planar graphs
• Labelings vs. embeddings: on distributed and prioritized representations of distances
• Implicit representation of relations
• Distance labeling for families of cycles
• Closing the gap: minimum space optimal time distance labeling scheme for interval graphs
• Optimal distance labeling for permutation graphs
• Better distance labeling for unweighted planar graphs

This page was built for publication: Distance labeling schemes for trees

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