Average case analysis for tree labelling schemes

详细信息    查看全文

• 作者：Ming-Yang Kao ; Xiang-Yang Li ; Weizhao Wang
• 关键词：Tree labelling ; Average case analysis ; Separator
• 刊名：Theoretical Computer Science
• 出版年：2007
• 出版时间：9 June 2007
• 年：2007
• 卷：378
• 期：3
• 页码：271-291
• 全文大小：554 K

文摘

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 bits, where NG3-1&_mathId=mml2&_user=10&_cdi=5674&_rdoc=6&_acct=C000050221&_version=1&_userid=10&md5=3a010f5fb14ab29d986d588a04236814"" title=""Click to view the MathML source"">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 Θ(lognlog(H_n(T))), where H_n(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.