| 密钥覆盖问题的建模、变换及近似算法 |
| |
| 引用本文： | 陆正福,洪孙焱.密钥覆盖问题的建模、变换及近似算法[J].小型微型计算机系统,2007,28(7):1189-1194. |
| |
| 作者姓名： | 陆正福 洪孙焱 |
| |
| 作者单位： | 云南大学,数学系,云南,昆明,650091 |
| |
| 基金项目： | 国家自然科学基金;云南省自然科学基金;云南大学校科研和教改项目;云南大学校科研和教改项目 |
| |
| 摘 要： | 组密钥管理是组安全、多播安全中的核心问题.本文给出了密钥覆盖问题模型的建立过程,首次给出密钥覆盖问题（KCP）与顶点覆盖问题（VCP）的相互变换.基于从VCP到KCP的变换,证明了密钥覆盖问题是NP完全的;基于从KCP到VCP的变换,基于VCP的算法为KCP设计了一类近似算法并给出了模拟试验.本文的结果为组安全、多播安全研究提供了更为坚实的算法基础.
|
| 关 键 词： | 组密钥管理 组合优化 计算复杂性 顶点覆盖问题 密钥覆盖问题 密钥图 |
| 文章编号： | 1000-1220（2007）07-1189-06 |
| 修稿时间： | 2006-04-17 |
On the Modeling Transformations and Approximation Algorithms of Key Covering Problem in the Group Rekeying |
| |
| LU Zheng-fu,HONG Sun-yan.On the Modeling Transformations and Approximation Algorithms of Key Covering Problem in the Group Rekeying[J].Mini-micro Systems,2007,28(7):1189-1194. |
| |
| Authors: | LU Zheng-fu HONG Sun-yan |
| |
| Affiliation: | Department of Mathematics,Yunnan University,Kunming 650091 ,China |
| |
| Abstract: | Group key management is essential for group security,especially for multicast security.This paper presents the modeling process of the key covering problem(KCP) in the group rekeying and the transformations between the KCP and the vertex covering problem(VCP) in the graph theory.Furthermore,based on the transformation from the VCP to the KCP,the NP-completeness of the decision version of the KCP is proved via the decision version of the VCP;Based on the transformation from the KCP to the VCP,the approximation algorithms for the KCP is designed via the greedy approximation algorithms for the VCP and the simulation is also given.The results of this paper lay a more solid algorithmic foundation for the research of group security,especially of multicast security. |
| |
| Keywords: | group key management combinatorial optimization computational complexity vertex covering problem key covering problem key graph |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
