摘要
图排序问题在众多领域中有着重要应用,本文利用多层次思想,提出一种具有V-循环结构的新算法,该算法是一种线性时间复杂度的方法.在文中的4个算例中,这种多层次方法所得到的排序质量至少比谱方法高5%,本文把它应用到图剖分领域,利用KL/FM方法对其进行了局部修改,得到了两种新的图剖分算法.在文中的4个算例中,这两种方法都能提供与当前质量最佳算法相当的图剖分结果。
Finding a linear ordering of the vertices of a graph is a common problem arising in diverse applications. In this paper, we present a linear time algorithm under the multi-level framework. Experiments show that our algorithm produces results at least 5% better than spectral method, which is the most popular algorithm. Furthermore, we construct two new graph partitioning algorithms by combining the above algorithm with KL/FM algorithm. Experimental results are similar to those of the best known approaches.
出处
《数值计算与计算机应用》
CSCD
2008年第3期226-240,共15页
Journal on Numerical Methods and Computer Applications
基金
国家杰出青年基金(60425205)
国家973项目(2005CB321702)
关键词
图排序问题
多层次方法
图剖分问题
Minimum linear arrangement, Multi-level algorithm, Graph partitioning problem
