Browsing by Author "Huang, Scott C.-H."

Now showing 1 - 2 of 2
  • Thumbnail Image
    Item
    Maximal Independent Set and Minimum Connected Dominating Set in Unit Disk Graphs
    (2004-12-13) WuLi, Wei; Du, Hongwei; Jia, Xiaohua; Li, Yingshu; Huang, Scott C.-H.; Du, Ding-Zhu
    In ad hoc wireless networks, the connected dominating set can be used as a virtual backbone to improve the performance. Many constructions for approximating the minimum connected dominating set are based on construction of maximal independent set. The relation between the size mis(G) of a maximum independent set and the size cds(G) of minimum connected dominating set in the same graph G plays an important role in establishing the performance ratio of those approximation algorithms. Previously, it is known that mis(G)<=4*cds(G)+1 for all unit disk graph G. In this paper, we improve it by showing mis(G)<=3.8*cds(G)+1.2.
  • Thumbnail Image
    Item
    New Constructions On Broadcast Encryption and Key Pre-Distribution Schemes
    (2004-06-24) Huang, Scott C.-H.; Du, Ding-Zhu
    This paper presents various new techniques on secure group communication schemes. We present a new broadcast encryption scheme Arachne, being particularly efficient in multiple revocation, and a node-based key pre-distribution scheme, remedying the key overlapping problem of pool-based schemes. Starting with a detailed analysis on broadcast encryption and group key distribution schemes, we discuss the influence of emph{join} as well as the feasibility of including it in broadcast encryption schemes by means of performing full updating or overprovisioning.