多层次图排序算法及其在图剖分中的应用

摘要：

图排序问题在众多领域中有着重要应用.本文利用多层次思想,提出一种具有V-循环结构的新算法.该算法是一种线性时间复杂度的方法.在文中的4个算例中,这种多层次方法所得到的排序质量至少比谱方法高5%.本文把它应用到图剖分领域,利用KL/FM方法对其进行了局部修改,得到了两种新的图剖分算法.在文中的4个算例中,这两种方法都能提供与当前质量最佳算法相当的图剖分结果.

关键词：图排序问题、多层次方法、图剖分问题

所属期刊栏目：29

分类号：TP3;O17

资助基金：国家杰出青年基金60425205;国家973项目2005CB321702

在线出版日期：2008-11-07（万方平台首次上网日期，不代表论文的发表时间）

页数：共15页

页码：226-240