互联网 qkzz.net
全刊杂志网:首页 > 女性 > 文章正文
刊社推荐

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


□ 冷 明 孙凌宇 郁松年

  摘 要:在多水平方法初始剖分阶段提出了一种基于谱方法的无向赋权图剖分算法SPWUG,给出了基于Lanczos迭代计算Laplacian矩阵次小特征值及特征向量的实现细节。SPWUG算法借助Laplacian矩阵次小特征值对应的特征向量,刻画了节点间相对距离,将基于非赋权无向图的Laplacian谱理论在图的剖分应用方面扩展到无向赋权图上,实现了对最小图的初始剖分。基于ISPD98电路测试基准的实验表明,SPWUG算法取得了一定性能的改进。实验分析反映了在多水平方法中,最小图上的全局近似最优剖分可能是初始图的局部最优剖分,需要加强优化阶段的迁移优化算法逃离局部最优的能力。
  关键词:多水平方法; 剖分; 无向赋权图; 谱方法
  中图分类号:TP391文献标志码:A
  文章编号:1001-3695(2009)06-2086-04
  doi:10.3969/j.issn.1001-3695.2009.06.025
  
  Spectral-based weighted undirected graph partitioning algorithm
  LENG Ming1,2, SUN Ling-yu1, YU Song-nian2
  (1. Dept. of Computer Science, Jinggangshan University, Ji’an Jiangxi 343009, China;2.School of Computer Engineering & Science,Shanghai University,Shanghai 200072, China)
  Abstract:During the initial partitioning phase of multilevel method, this paper proposed the algorithm of spectral partitioning for weighted undirected graph (SPWUG) and gave the Fiedler vector calculation of Laplacian matrix using the Lanczos iteration method. The components of the Fiedler vector were weighted on the corresponding vertices of graph such that differences of the components provide information about the distances between the vertices. According to the distances, the SPWUG algorithm computed the initial partition of the coarsest graph by extending the Laplacian spectral graph theory from the unweighted undirected graph into the weighted undirected graph. The experimental evaluations show that the SPWUG algorithm produces the performance improvement. Meanwhile, the analysis shows that the approximate global minimum partition of the coarsest graph may be the local minimum partition of the finest graph and need to strengthen the global search ability of refinement algorithm in the refinement phase. ......
很抱歉,暂无全文,若需要阅读全文或喜欢本刊物请联系《计算机应用研究》杂志社购买。
欢迎作者提供全文,请点击编辑
分享:
 

了解更多资讯,请关注“木兰百花园”
分享:
 
精彩图文


关键字
支持中国杂志产业发展,请购买、订阅纸质杂志,欢迎杂志社提供过刊、样刊及电子版。
关于我们 | 网站声明 | 刊社管理 | 网站地图 | 联系方式 | 中图分类法 | RSS 2.0订阅 | IP查询
全刊杂志赏析网 2017