%0 Journal Article
%T 基于ncut准则的图分割的新算法
%A 周德新
%A 王兴旺
%A 刘涛
%J 计算机应用
%D 2010
%X ？针对有权图分割时不能很好解决子图内部耦合度不高的问题，使用可以同时优化子图内部顶点耦合度和子图之间顶点耦合度的ncut准则，提出了一种新的基于迭代改善策略的rnk分割算法。算法通过不断交换可以改善ncut值的顶点对优化现有分割。与传统分割算法相比，可以同时保证子图内最大耦合度和子图间最小的耦合度。并提出一种散列技术，提高查找最优交换顶点对的效率。当图为稠密矩阵时，改善效果尤为明显。通过对随机图分割的实验结果表明，该算法较传统的kl算法可以得到更理想的分割结果。
%K 图分割
%K 耦合度
%K ncut准则
%K 散列
%U http://www.joca.cn/CN/abstract/abstract13413.shtml