Advertisement
Published in:
2005 | OriginalPaper | Chapter
Average Case Analysis for Tree Labelling Schemes
Authors : Ming-Yang Kao, Xiang-Yang Li, WeiZhao Wang
Published in: Algorithms and Computation
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
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 \over 8} {\rm log}^{2} n - O({\rm log} n)$
bits. They also gave a separator-based labelling scheme that has the optimal label length
${\it \Theta}({\rm log} {n} \cdot {\rm log}(H_{n}(T)))$
, where
H
n
(
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
${\it \Theta}({\rm log} n \cdot {\rm log} (H_{n}(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.