Optimal tree structures for group key tree management considering insertion and deletion cost

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journal

6 Scopus Citations
View graph of relations

Author(s)

Related Research Unit(s)

Detail(s)

Original languageEnglish
Pages (from-to)2619-2631
Journal / PublicationTheoretical Computer Science
Volume410
Issue number27-29
Online published10 Mar 2009
Publication statusPublished - 28 Jun 2009

Abstract

We study the optimal structure for the 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 (n2) time. In this paper, we first prove a semi-balance property for the optimal tree and use it to reduce the running time from (n2) to O(log log n) multiplications of (log n)-bit integers. 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 degree at most 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.

Research Area(s)

  • Group keys, Key trees, Optimality, Updating cost