基于谱方法的无向赋权图剖分算法

• 作者: 冷明 孙凌宇 郁松年
• 来源期刊: 计算机应用研究
• 关键词: 多水平方法 剖分 无向赋权图 谱方法
• 年，卷（期）: 2009,（6）
• 所属期刊栏目: 算法研究探讨
• 页码范围: 2086-2089
• 页数: 4页
• 分类号: TP391
• 语种: 中文
• DOI: 10.3969/j.issn.1001-3695.2009.06.025

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	孙凌宇	井冈山大学计算机科学系	46	236	7.0	12.0
2	冷明	井冈山大学计算机科学系	52	211	7.0	11.0
6	郁松年	上海大学计算机工程与科学学院	23	90	6.0	8.0