Optimal Tree Structures for Group Key Tree Management Considering Insertion and Deletion Cost

Research output: Chapters, Conference Papers, Creative and Literary Works (RGC: 12, 32, 41, 45)32_Refereed conference paper (with ISBN/ISSN)

1 Scopus Citations
View graph of relations

Author(s)

Related Research Unit(s)

Detail(s)

Original languageEnglish
Title of host publicationComputing and Combinatorics
Subtitle of host publication14th Annual International Conference, COCOON 2008, Proceedings
EditorsXiaodong Hu, Jie Wang
PublisherSpringer Verlag
Pages521-530
ISBN (Electronic)9783540697336
ISBN (Print)3540697322, 9783540697329
Publication statusPublished - Jun 2008

Publication series

NameLecture Notes in Computer Science
Volume5092
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Title14th Annual International Conference on Computing and Combinatorics (COCOON 2008)
PlaceChina
CityDalian
Period27 - 29 June 2008

Abstract

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 (n2) to (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 (n2) time to compute the optimal tree.

Citation Format(s)

Optimal Tree Structures for Group Key Tree Management Considering Insertion and Deletion Cost. / Wu, Weiwei; Li, Minming; Chen, Enhong.

Computing and Combinatorics: 14th Annual International Conference, COCOON 2008, Proceedings. ed. / Xiaodong Hu; Jie Wang. Springer Verlag, 2008. p. 521-530 (Lecture Notes in Computer Science; Vol. 5092).

Research output: Chapters, Conference Papers, Creative and Literary Works (RGC: 12, 32, 41, 45)32_Refereed conference paper (with ISBN/ISSN)