Optimal Tree Structures for Group Key Tree Management Considering Insertion and Deletion Cost
We study the optimal structure for group broadcast problem where the key tree model is extensively used. The objective is usually to find an optimal key tree to minimize the cost based on certain assumptions. Under the assumption that n members arrive in the initial setup period and only member deletions are allowed after that period, previous works show that when only considering the deletion cost, the optimal tree can be computed in O(n2) time. In this paper, we first prove a semi-balance property for the optimal tree and use it to improve the running time from O (n2) to O(log log n). Then we study the optimal tree structure when insertion cost is also considered. We show that the optimal tree is such a tree where any internal node has at most degree 7 and children of nodes with degree not equal to 2 or 3 are all leaves. Based on this result we give a dynamic programming algorithm with O(n2) time to compute the optimal tree.
Weiwei Wu Minming Li Enhong Chen
USTC-CityU Joint Research Institute Department of Computer Science,University of Science and Technol Department of Computer Science, City University of Hong Kong Department of Computer Science, University of Science and Technology of China
国际会议
The 4th Annual International Computing and Combinatorics Conference,COCOON 2008(第14届国际计算和组合会议)
大连
英文
521-530
2008-06-01（万方平台首次上网日期，不代表论文的发表时间）