Average case analysis for tree labelling schemes

Ming-Yang Kao*, Xiang Yang Li, Weizhao Wang

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations


We study how to label the vertices of a tree in such a way that we can decide the distance of two vertices in the tree given only their labels. For trees, Gavoille et al. [7] proved that for any such distance labelling scheme, the maximum label length is at least 1/8 log2 n - O(log n) bits. They also gave a separator-based labelling scheme that has the optimal label length Θ(log n · log(Hn(T))), where Hn(T) is the height of the tree. In this paper, we present two new distance labelling schemes that not only achieve the optimal label length Θ (log n · log(Hn(T))), but also have a much smaller expected label length under certain tree distributions. With these new schemes, we also can efficiently find the least common ancestor of any two vertices based on their labels only.

Original languageEnglish (US)
Title of host publicationAlgorithms and Computation - 16th International Symposium, ISAAC 2005, Proceedings
Number of pages10
StatePublished - 2005
Event16th International Symposium on Algorithms and Computation, ISAAC 2005 - Hainan, China
Duration: Dec 19 2005Dec 21 2005

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume3827 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other16th International Symposium on Algorithms and Computation, ISAAC 2005

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'Average case analysis for tree labelling schemes'. Together they form a unique fingerprint.

Cite this