论文部分内容阅读
图划分问题是一个NP完全问题，很难在多项式时间内获得一个最优解。为快速获得一个图划分的近似最优解，研究了信息论中的相关知识，设计了一个基于信息论的求解图K划分的近似算法。该算法通过快速求解各节点的自信息及熵，获得各节点集之间的相关性，从而获得相应的划分。经分析，该算法的时间复杂度为O（V2）。实验结果表明，该算法获得的解同工具metis的求解效果相当，且在时间上明显优于metis工具。