TY - GEN
T1 - Optimal Tree Structures for Group Key Tree Management Considering Insertion and Deletion Cost
AU - Wu, Weiwei
AU - Li, Minming
AU - Chen, Enhong
PY - 2008/6
Y1 - 2008/6
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=48249117044&partnerID=8YFLogxK
UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-48249117044&origin=recordpage
U2 - 10.1007/978-3-540-69733-6_51
DO - 10.1007/978-3-540-69733-6_51
M3 - 32_Refereed conference paper (with ISBN/ISSN)
SN - 3540697322
SN - 9783540697329
T3 - Lecture Notes in Computer Science
SP - 521
EP - 530
BT - Computing and Combinatorics
A2 - Hu, Xiaodong
A2 - Wang, Jie
PB - Springer Verlag
T2 - 14th Annual International Conference on Computing and Combinatorics (COCOON 2008)
Y2 - 27 June 2008 through 29 June 2008
ER -