TY - JOUR
T1 - Average case analysis for tree labelling schemes
AU - Kao, Ming-Yang
AU - Li, Xiang Yang
AU - Wang, Weizhao
N1 - Funding Information:
First author’s research supported in part by NSF Grant IIS-0121491.
PY - 2007/6/9
Y1 - 2007/6/9
N2 - 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. Gavoille et al. proved that for any such distance labelling scheme, the maximum label length is at least frac(1, 8) log2 n - O (log n) bits, where n is the number of vertices in the input tree T. They also gave a separator-based labelling scheme that has the optimal label length Θ (log n {dot operator} log (Hn (T))), where Hn (T) is the height of T. We present two distance labelling schemes, namely, the backbone-based scheme and rake-based scheme, which also achieve the optimal label length. The two schemes always perform at least as well as the separator scheme. Furthermore, the rake-based scheme has a much smaller expected label length under certain tree distributions. With these new schemes, we also can find the least common ancestor of any two vertices based on their labels only.
AB - 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. Gavoille et al. proved that for any such distance labelling scheme, the maximum label length is at least frac(1, 8) log2 n - O (log n) bits, where n is the number of vertices in the input tree T. They also gave a separator-based labelling scheme that has the optimal label length Θ (log n {dot operator} log (Hn (T))), where Hn (T) is the height of T. We present two distance labelling schemes, namely, the backbone-based scheme and rake-based scheme, which also achieve the optimal label length. The two schemes always perform at least as well as the separator scheme. Furthermore, the rake-based scheme has a much smaller expected label length under certain tree distributions. With these new schemes, we also can find the least common ancestor of any two vertices based on their labels only.
KW - Average case analysis
KW - Separator
KW - Tree labelling
UR - http://www.scopus.com/inward/record.url?scp=34248231997&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=34248231997&partnerID=8YFLogxK
U2 - 10.1016/j.tcs.2007.02.066
DO - 10.1016/j.tcs.2007.02.066
M3 - Article
AN - SCOPUS:34248231997
SN - 0304-3975
VL - 378
SP - 271
EP - 291
JO - Theoretical Computer Science
JF - Theoretical Computer Science
IS - 3
ER -