多层次图排序算法及其在图剖分中的应用
图排序问题在众多领域中有着重要应用.本文利用多层次思想,提出一种具有V-循环结构的新算法.该算法是一种线性时间复杂度的方法.在文中的4个算例中,这种多层次方法所得到的排序质量至少比谱方法高5%.本文把它应用到图剖分领域,利用KL/FM方法对其进行了局部修改,得到了两种新的图剖分算法.在文中的4个算例中,这两种方法都能提供与当前质量最佳算法相当的图剖分结果.
作 者： 刘旭 莫则尧 Liu Xu Mo Zeyao 作者单位： 刘旭,Liu Xu(中国工程物理研究院研究生部,北京,100088;北京应用物理与计算数学研究所高性能计算中心,北京,100088)莫则尧,Mo Zeyao(北京应用物理与计算数学研究所高性能计算中心,北京,100088)
刊 名： 数值计算与计算机应用 ISTIC PKU 英文刊名： JOURNAL ON NUMERICAL METHODS AND COMPUTER APPLICATIONS 年，卷(期)： 2008 29(3) 分类号： O1 关键词： 图排序问题 多层次方法 图剖分问题