基于信息论的图K划分方法
图划分问题是一个NP完全问题,很难在多项式时间内获得一个最优解.为快速获得一个图划分的近似最优解,研究了信息论中的相关知识,设计了一个基于信息论的求解图K划分的近似算法.该算法通过快速求解各节点的自信息及熵,获得各节点集之间的相关性,从而获得相应的划分.经分析,该算法的时间复杂度为O(V2).实验结果表明,该算法获得的解同工具metis的求解效果相当,且在时间上明显优于metis工具.
图K划分、熵、自信息、信息论、NP难
32
TP301.6(计算技术、计算机技术)
江苏省2010年高校科研成果产业化推进基金项目JHZD10-023
2012-03-16(万方平台首次上网日期,不代表论文的发表时间)
共5页
3738-3741,3788