1 Search Results for "Halvorsen, Esben Bistrup"

Document

DOI: 10.4230/LIPIcs.ICALP.2016.132

Distance Labeling Schemes for Trees

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

Published in: LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)

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. [Gavoille et al., J. Alg., 2004] and an upper bound by Peleg [Peleg, J. Graph Theory, 2000] establish that labels must use Theta(log^2(n)) bits. Gavoille et al. [Gavoille et al., ESA, 2001] show that for very small approximate stretch, labels use Theta(log(n) log(log(n))) bits. Several other papers investigate various variants such as, for example, small distances in trees [Alstrup et al., SODA, 2003]. We improve the known upper and lower bounds of exact distance labeling by showing that 1/4*log^2(n) bits are needed and that 1/2*log^2(n) bits are sufficient. We also give (1 + epsilon)-stretch labeling schemes using Theta(log(n)) bits for constant epsilon > 0. (1 + epsilon)-stretch labeling schemes with polylogarithmic label size have previously been established for doubling dimension graphs by Talwar [Talwar, STOC, 2004]. In addition, we present matching upper and lower bounds for distance labeling for caterpillars, showing that labels must have size 2*log(n) - Theta(log(log(n))). For simple paths with k nodes and edge weights in [1,n], we show that labels must have size (k - 1)/k*log(n) + Theta(log(k)).

Cite as

Stephen Alstrup, Inge Li Gørtz, Esben Bistrup Halvorsen, and Ely Porat. Distance Labeling Schemes for Trees. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 132:1-132:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{alstrup_et_al:LIPIcs.ICALP.2016.132,
  author =	{Alstrup, Stephen and G{\o}rtz, Inge Li and Halvorsen, Esben Bistrup and Porat, Ely},
  title =	{{Distance Labeling Schemes for Trees}},
  booktitle =	{43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
  pages =	{132:1--132:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-013-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{55},
  editor =	{Chatzigiannakis, Ioannis and Mitzenmacher, Michael and Rabani, Yuval and Sangiorgi, Davide},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.132},
  URN =		{urn:nbn:de:0030-drops-62661},
  doi =		{10.4230/LIPIcs.ICALP.2016.132},
  annote =	{Keywords: Distributed computing, Distance labeling, Graph theory, Routing, Trees}
}

Refine by Author
1 Alstrup, Stephen
1 Gørtz, Inge Li
1 Halvorsen, Esben Bistrup
1 Porat, Ely

Refine by Classification

Refine by Keyword
1 Distance labeling
1 Distributed computing
1 Graph theory
1 Routing
1 Trees

Refine by Type
1 document

Refine by Publication Year
1 2016

1 Search Results for "Halvorsen, Esben Bistrup"

Distance Labeling Schemes for Trees

Abstract

Cite as

Thanks for your feedback!

Could not send message