Average case analysis for tree labelling schemes

作     者：Kao, Ming-Yang Li, Xiang-Yang Wang, Weizhao 

作者机构：IIT Dept Comp Sci Chicago IL 60616 USA Northwestern Univ Dept Elect Engn & Comp Sci Evanston IL 60208 USA 

出 版 物：《THEORETICAL COMPUTER SCIENCE》 (Theor Comput Sci)

年 卷 期：2007年第378卷第3期

页      面：271-291页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：National Science Foundation  NSF  (IIS-0121491  IIS-0121491) 

主　　题：tree labelling average case analysis separator 

摘      要：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 1/8 log(2) 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 8 that has the optimal label length Theta (log n center dot log(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. (c) 2007 Elsevier B.V. All rights reserved.