|
|||||
|
|
| 基于信息论的图K划分方法 | |
| 引用本文： | 朱作付,徐超,钱俊. 基于信息论的图K划分方法[J]. 计算机工程与设计, 2011, 32(11): 3738-3741,3788 |
| 作者姓名： | 朱作付 徐超 钱俊 |
| 作者单位： | 1. 徐州工业职业技术学院信息工程系,江苏徐州,221000 2. 徐州工业职业技术学院信息工程系,江苏徐州221000;武汉大学计算机学院,湖北武汉430072 3. 武汉大学计算机学院,湖北武汉,430072 |
| 基金项目： | 江苏省2010年高校科研成果产业化推进基金项目 |
| 摘 要： | 图划分问题是一个NP完全问题,很难在多项式时间内获得一个最优解。为快速获得一个图划分的近似最优解,研究了信息论中的相关知识,设计了一个基于信息论的求解图K划分的近似算法。该算法通过快速求解各节点的自信息及熵,获得各节点集之间的相关性,从而获得相应的划分。经分析,该算法的时间复杂度为O(V2)。实验结果表明,该算法获得的解同工具metis的求解效果相当,且在时间上明显优于metis工具。 |
| 关 键 词： | 图K划分 熵 自信息 信息论 NP难 |
Graph K-partitions based on information theory |
|
| ZHU Zuo-fu,XU Chao,QIAN Jun. Graph K-partitions based on information theory[J]. Computer Engineering and Design, 2011, 32(11): 3738-3741,3788 | |
| Authors: | ZHU Zuo-fu XU Chao QIAN Jun |
| Affiliation: | ZHU Zuo-fu1,XU Chao1,2,QIAN Jun2(1.Department of Information Engineering,Xuzhou College of Industrial Technology,Xuzhou 221000,China,2.School of Computer,Wuhan University,Wuhan 430072,China) |
| Abstract: | The graph partition is a NP-hard problem,and it is hard to find an optimal algorithm that using only polynomial time complexity.To get a faster algorithm,the relevant knowledge in information theory is studied and an approximate algorithm for the K-partition problem using theory of information area is designed.The relationship of nodes is gotten by the calculation of self-information and entropy and the partition is layout by the relationship of nodes.For the analysis,its time complexity is only O(V2).Exper... |
| Keywords: | K-partition graph entropy self-information information theory NP-hard |
| 本文献已被 CNKI 万方数据 等数据库收录！ | |