文献类型：期刊文章

作　　者：冷明[1,2] 孙凌宇[1] 郁松年[2]

机构地区：[1]井冈山大学计算机科学系,江西吉安343009 [2]上海大学计算机工程与科学学院,上海200072

出　　处：《计算机应用研究》

基　　金：科技部国际合作项目(CB7-2-01);上海市教育委员会科研创新资助项目(08YZ13);江西省教育厅科学技术研究项目(GJJ09590)

年　　份：2009

卷　　号：26

期　　号：6

起止页码：2086-2089

语　　种：中文

收录情况：AJ、BDHX、BDHX2008、CSA-PROQEUST、CSCD、CSCD2011_2012、IC、INSPEC、JST、RCCSE、UPD、ZGKJHX、ZMATH、核心刊

摘　　要：在多水平方法初始剖分阶段提出了一种基于谱方法的无向赋权图剖分算法SPWUG,给出了基于Lanc-zos迭代计算Laplacian矩阵次小特征值及特征向量的实现细节。SPWUG算法借助Laplacian矩阵次小特征值对应的特征向量,刻画了节点间相对距离,将基于非赋权无向图的Laplacian谱理论在图的剖分应用方面扩展到无向赋权图上,实现了对最小图的初始剖分。基于ISPD98电路测试基准的实验表明,SPWUG算法取得了一定性能的改进。实验分析反映了在多水平方法中,最小图上的全局近似最优剖分可能是初始图的局部最优剖分,需要加强优化阶段的迁移优化算法逃离局部最优的能力。

关 键 词：多水平方法  剖分 无向赋权图 谱方法

分 类 号：TP391]