Document Open Access Logo

Distance Labeling Schemes for Trees

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

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2016.132.pdf
  • Filesize: 0.54 MB
  • 16 pages

Document Identifiers

Author Details

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

Cite As Get BibTex

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) https://doi.org/10.4230/LIPIcs.ICALP.2016.132

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)).

Subject Classification

Keywords
  • Distributed computing
  • Distance labeling
  • Graph theory
  • Routing
  • Trees

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. S. Abiteboul, S. Alstrup, H. Kaplan, T. Milo, and T. Rauhe. Compact labeling scheme for ancestor queries. SIAM J. Comput., 35(6):1295-1309, 2006. URL: http://dx.doi.org/10.1137/S0097539703437211.
  2. S. Abiteboul, H. Kaplan, and T. Milo. Compact labeling schemes for ancestor queries. In Proc. of the 12th Annual ACM-SIAM Symp. on Discrete Algorithms (SODA), pages 547-556, 2001. Google Scholar
  3. N. Alon, F .R. K. Chung, and R. L. Graham. Routing permutations on graphs via matchings. In Proc. of the 25th Annual ACM Symp. on the Theory of Computing (STOC), pages 583-591, 1993. Google Scholar
  4. S. Alstrup, P. Bille, and T. Rauhe. Labeling schemes for small distances in trees. In Proc. of the 14th Annual ACM-SIAM Symp. on Discrete Algorithms (SODA), pages 689-698, 2003. URL: http://dl.acm.org/citation.cfm?id=644108.644220.
  5. S. Alstrup, P. Bille, and T. Rauhe. Labeling schemes for small distances in trees. SIAM J. Discrete Math., 19(2):448-462, 2005. See also SODA'03. URL: http://dx.doi.org/10.1137/S0895480103433409.
  6. S. Alstrup, S. Dahlgaard, and M. B. T. Knudsen. Optimal induced universal graphs and labeling schemes for trees. In Proc. 56th Annual Symp. on Foundations of Computer Science (FOCS), 2015. Google Scholar
  7. S. Alstrup, C. Gavoile, E. B. Halvorsen, and H. Petersen. Simpler, faster and shorter labels for distances in graphs. In Proc. of the 27th Annual ACM-SIAM Symp. on Discrete Algorithms (SODA), 2016. Google Scholar
  8. S. Alstrup, C. Gavoille, H. Kaplan, and T. Rauhe. Nearest common ancestors: A survey and a new algorithm for a distributed environment. Theory of Computing Systems, 37(3):441-456, 2004. URL: http://dx.doi.org/10.1007/s00224-004-1155-5.
  9. S. Alstrup, E. B. Halvorsen, and K. G. Larsen. Near-optimal labeling schemes for nearest common ancestors. In Proc. of the 25th Annual ACM-SIAM Symp. on Discrete Algorithms (SODA), pages 972-982, 2014. URL: http://dx.doi.org/10.1137/1.9781611973402.72.
  10. S. Alstrup, J. Holm, K. de Lichtenberg, and M. Thorup. Direct routing on trees. In Proc. of the 9th Annual ACM-SIAM Symp. on Discrete Algorithms (SODA), pages 342-349, 1998. Google Scholar
  11. S. Alstrup, H. Kaplan, M. Thorup, and U. Zwick. Adjacency labeling schemes and induced-universal graphs. In Proc. of the 47th Annual ACM Symp. on Theory of Computing (STOC), 2015. Google Scholar
  12. S. Alstrup and T. Rauhe. Improved labeling schemes for ancestor queries. In Proc. of the 13th Annual ACM-SIAM Symp. on Discrete Algorithms (SODA), 2002. Google Scholar
  13. S. Alstrup and T. Rauhe. Small induced-universal graphs and compact implicit graph representations. In Proc. 43rd Annual Symp. on Foundations of Computer Science (FOCS), pages 53-62, 2002. Google Scholar
  14. F. Bazzaro and C. Gavoille. Localized and compact data-structure for comparability graphs. Discrete Mathematics, 309(11):3465-3484, 2009. URL: http://dx.doi.org/10.1016/j.disc.2007.12.091.
  15. N. Bonichon, C. Gavoille, and A. Labourel. Short labels by traversal and jumping. In Structural Information and Communication Complexity, pages 143-156. Springer, 2006. Include proof for binary trees and caterpillars. Google Scholar
  16. M. A. Breuer. Coding the vertexes of a graph. IEEE Trans. on Information Theory, IT-12:148-153, 1966. Google Scholar
  17. M. A. Breuer and J. Folkman. An unexpected result on coding vertices of a graph. J. of Mathemathical analysis and applications, 20:583-600, 1967. Google Scholar
  18. V. D. Chepoi, F. F. Dragan, B. Estellon, M. Habib, and Y. Vaxès. Diameters, centers, and approximating trees of delta-hyperbolic geodesic spaces and graphs. In 24st Annual ACM Symp. on Computational Geometry (SoCG), pages 59-68, 2008. URL: http://dx.doi.org/10.1145/1377676.1377687.
  19. V. D. Chepoi, F. F. Dragan, and Y. Vaxès. Distance and routing labeling schemes for non-positively curved plane graphs. J. of Algorithms, 61(2):60-88, 2006. URL: http://dx.doi.org/10.1016/j.jalgor.2004.07.011.
  20. F. R. K. Chung. Universal graphs and induced-universal graphs. J. of Graph Theory, 14(4):443-454, 1990. Google Scholar
  21. E. Cohen, H. Kaplan, and T. Milo. Labeling dynamic XML trees. SIAM J. Comput., 39(5):2048-2074, 2010. URL: http://dx.doi.org/10.1137/070687633.
  22. B. Courcelle and R. Vanicat. Query efficient implementation of graphs of bounded clique-width. Discrete Applied Mathematics, 131:129-150, 2003. URL: http://dx.doi.org/10.1016/S0166-218X(02)00421-3.
  23. L. J. Cowen. Compact routing with minimum stretch. J. of Algorithms, 38:170-183, 2001. See also SODA'91. Google Scholar
  24. Y. Dodis, M. Pǎtraşcu, and M. Thorup. Changing base without losing space. In Proc. of the 42nd Annual ACM Symp. on Theory of Computing (STOC), pages 593-602, 2010. Google Scholar
  25. T. Eilam, C. Gavoille, and D. Peleg. Compact routing schemes with low stretch factor. J. of Algorithms, 46(2):97-114, 2003. URL: http://dx.doi.org/10.1016/S0196-6774(03)00002-6.
  26. M. Elkin, A. Filtser, and O. Neiman. Prioritized metric structures and embedding. In Proc. of the 47th Annual ACM Symp. on Theory of Computing (STOC), pages 489-498, 2015. Google Scholar
  27. A. Farzan and J. I. Munro. Succinct encoding of arbitrary graphs. Theoretical Computer Science, 513:38-52, 2013. URL: http://dx.doi.org/10.1016/j.tcs.2013.09.031.
  28. A. Farzan and J. I. Munro. A uniform paradigm to succinctly encode various families of trees. Algorithmica, 68(1):16-40, 2014. URL: http://dx.doi.org/10.1007/s00453-012-9664-0.
  29. P. Fraigniaud and A. Korman. On randomized representations of graphs using short labels. In Proc. of the 21st Annual Symp. on Parallelism in Algorithms and Architectures (SPAA), pages 131-137, 2009. URL: http://dx.doi.org/10.1145/1583991.1584031.
  30. P. Fraigniaud and A. Korman. Compact ancestry labeling schemes for XML trees. In Proc. of the 21st annual ACM-SIAM Symp. on Discrete Algorithms (SODA), pages 458-466, 2010. Google Scholar
  31. P. Fraigniaud and A. Korman. An optimal ancestry scheme and small universal posets. In Proc. of the 42nd Annual ACM Symp. on Theory of Computing (STOC), pages 611-620, 2010. URL: http://dx.doi.org/10.1145/1806689.1806773.
  32. C. Gavoille, M. Katz, N. Katz, C. Paul, and D. Peleg. Approximate distance labeling schemes. In Proc. of the 9th Annual European Symp. on Algorithms (ESA), pages 476-488, 2001. Google Scholar
  33. C. Gavoille and A. Labourel. Distributed relationship schemes for trees. In 18th International Symp. on Algorithms and Computation (ISAAC), pages 728-738, 2007. URL: http://dx.doi.org/10.1007/978-3-540-77120-3_63.
  34. C. Gavoille and A. Labourel. On local representation of distances in trees. In Proc. of the 26th Annual ACM Symp. on Principles of Distributed Computing (PODC), pages 352-353, 2007. URL: http://dx.doi.org/10.1145/1281100.1281169.
  35. C. Gavoille and O. Ly. Distance labeling in hyperbolic graphs. In 16th Annual International Symp. on Algorithms and Computation (ISAAC), pages 1071-1079, 2005. URL: http://dx.doi.org/10.1007/11602613_106.
  36. C. Gavoille and C. Paul. Distance labeling scheme and split decomposition. Discrete Mathematics, 273(1-3):115-130, 2003. Google Scholar
  37. C. Gavoille and C. Paul. Optimal distance labeling for interval graphs and related graphs families. SIAM J. Discrete Math., 22(3):1239-1258, 2008. URL: http://dx.doi.org/10.1137/050635006.
  38. C. Gavoille, D. Peleg, S. Pérennes, and R. Raz. Distance labeling in graphs. In Proc. of the 12th Annual ACM-SIAM Symp. on Discrete algorithms (SODA), pages 210-219, 2001. URL: http://dl.acm.org/citation.cfm?id=365411.365447.
  39. C. Gavoille, D. Peleg, S. Pérennes, and R. Raz. Distance labeling in graphs. J. of Algorithms, 53(1):85-112, 2004. See also SODA'01. URL: http://dx.doi.org/10.1016/j.jalgor.2004.05.002.
  40. R. L. Graham and H. O. Pollak. On embedding graphs in squashed cubes. In Lecture Notes in Mathematics, volume 303. Springer-Verlag, 1972. Google Scholar
  41. A. Gupta, R. Krauthgamer, and J. R. Lee. Bounded geometries, fractals, and low-distortion embeddings. In 44th Annual Symp. on Foundations of Computer Science (FOCS), pages 534-543, 2003. URL: http://dx.doi.org/10.1109/SFCS.2003.1238226.
  42. A. Gupta, A. Kumar, and R. Rastogi. Traveling with a pez dispenser (or, routing issues in mpls). SIAM J. on Computing, 34(2):453-474, 2005. See also FOCS'01. Google Scholar
  43. E. B. Halvorsen. Labeling schemes for trees - overview and new results. Master’s thesis, University of Copenhagen, 2013. Available at URL: http://esben.bistruphalvorsen.dk.
  44. S. Kannan, M. Naor, and S. Rudich. Implicit representation of graphs. SIAM J. Disc. Math., pages 596-603, 1992. See also STOC'88. Google Scholar
  45. M. Kao, X. Li, and W. Wang. Average case analysis for tree labelling schemes. Theor. Comput. Sci., 378(3):271-291, 2007. URL: http://dx.doi.org/10.1016/j.tcs.2007.02.066.
  46. H. Kaplan and T. Milo. Short and simple labels for distances and other functions. In 7nd Work. on Algo. and Data Struc., 2001. Google Scholar
  47. H. Kaplan, T. Milo, and R. Shabo. A comparison of labeling schemes for ancestor queries. In Proc. of the 13th Annual ACM-SIAM Symp. on Discrete Algorithms (SODA), 2002. Google Scholar
  48. M. Katz, N. A. Katz, A. Korman, and D. Peleg. Labeling schemes for flow and connectivity. SIAM J. Comput., 34(1):23-40, 2004. See also SODA'02. URL: http://dx.doi.org/10.1137/S0097539703433912.
  49. A. Korman. Labeling schemes for vertex connectivity. ACM Trans. Algorithms, 6(2):39:1-39:10, 2010. URL: http://dx.doi.org/10.1145/1721837.1721855.
  50. A. Korman and S. Kutten. Labeling schemes with queries. CoRR, abs/cs/0609163, 2006. URL: http://arxiv.org/abs/cs/0609163.
  51. A. Korman and S. Kutten. Labeling schemes with queries. In SIROCCO, pages 109-123, 2007. Google Scholar
  52. A. Korman and D. Peleg. Labeling schemes for weighted dynamic trees. Inf. Comput., 205(12):1721-1740, 2007. URL: http://dx.doi.org/10.1016/j.ic.2007.08.004.
  53. R. Krauthgamer and J. R. Lee. Algorithms on negatively curved spaces. In 47th Annual Symp. on Foundations of Computer Science (FOCS), pages 119-132, 2006. URL: http://dx.doi.org/10.1109/FOCS.2006.9.
  54. F. T. Leighton. Methods for message routing in parallel machines. In Proc. of the 24 Annual ACM Symp. on the Theory of Computing (STOC), pages 77-96, 1992. Google Scholar
  55. M. Mitzenmacher. Constant time per edge is optimal on rooted tree networks. In Proc. of the 8th Annual ACM Symp. on parallel algorithms and Architectures (SPAA'96), pages 162-169, 1996. Google Scholar
  56. J. W. Moon. On minimal n-universal graphs. Proc. of the Glasgow Mathematical Association, 7(1):32-33, 1965. Google Scholar
  57. J. H. Müller. Local structure in graph classes. PhD thesis, Georgia Institute of Technology, 1988. Google Scholar
  58. J. I. Munro, R. Raman, V. Raman, and S. Srinivasa Rao. Succinct representations of permutations and functions. Theor. Comput. Sci., 438:74-88, 2012. URL: http://dx.doi.org/10.1016/j.tcs.2012.03.005.
  59. M. Pǎtraşcu. Succincter. In Proc. 49th Annual Symp. on Foundations of Computer Science (FOCS), pages 305-313, 2008. Google Scholar
  60. D. Peleg. Informative labeling schemes for graphs. In Proc. 25th Symp. on Mathematical Foundations of Computer Science, pages 579-588, 2000. Google Scholar
  61. D. Peleg. Proximity-preserving labeling schemes. J. Graph Theory, 33(3):167-176, 2000. Google Scholar
  62. N. Santoro and R. Khatib. Labeling and implicit routing in networks. The computer J., 28:5-8, 1985. Google Scholar
  63. D. D. Sleator and R. E. Tarjan. A data structure for dynamic trees. J. of Computer and System Sciences, 26(3):362-391, 1983. URL: http://dx.doi.org/10.1016/0022-0000(83)90006-5.
  64. J. P. Spinrad. Efficient Graph Representations, volume 19 of Fields Institute Monographs. AMS, 2003. Google Scholar
  65. K. Talwar. Bypassing the embedding: algorithms for low dimensional metrics. In Proc. of the 36th Annual ACM Symp. on Theory of Computing (STOC), pages 281-290, 2004. URL: http://dx.doi.org/10.1145/1007352.1007399.
  66. M. Tang, J. Yang, and G. Zhang. A compact distance labeling scheme for trees of small depths. In International Conference on Scalable Computing and Communications / Eighth International Conference on Embedded Computing, ScalCom-EmbeddedCom, pages 455-458, 2009. URL: http://dx.doi.org/10.1109/EmbeddedCom-ScalCom.2009.87.
  67. M. Thorup. Compact oracles for reachability and approximate distances in planar digraphs. J. ACM, 51(6):993-1024, 2004. See also FOCS'01. URL: http://dx.doi.org/10.1145/1039488.1039493.
  68. M. Thorup and U. Zwick. Compact routing schemes. In Proc. of the 13th Annual ACM Symp. on Parallel Algorithms and Architectures, SPAA'01, pages 1-10, 2001. URL: http://dx.doi.org/10.1145/378580.378581.
  69. M. Thorup and U. Zwick. Approximate distance oracles. J. of the ACM, 52(1):1-24, 2005. See also STOC'01. Google Scholar
  70. O. Weimann and D. Peleg. A note on exact distance labeling. Inf. Process. Lett., 111(14):671-673, 2011. URL: http://dx.doi.org/10.1016/j.ipl.2011.04.006.
  71. Wikipedia. Implicit graph - wikipedia, the free encyclopedia, 2013. [Online; accessed 15-February-2014]. URL: http://en.wikipedia.org/w/index.php?title=Implicit_graph&oldid=585232203.
  72. P. M. Winkler. Proof of the squashed cube conjecture. Combinatorica, 3(1):135-139, 1983. URL: http://dx.doi.org/10.1007/BF02579350.
  73. L. Zhang. Optimal bounds for matching routing on trees. In Proc. of the 8th Annual ACM-SIAM Symposium on discrete algorithms (SODA), pages 445-453, 1997. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact