论文研究 短块移动排序算法研究.pdf

将图核概念引入到多水平方法粗化阶段，针对图的压缩存储格式提出了核排序重边匹配（CSHEM）算法。该算法借助图核的全局信息，改进了以往仅仅利用结点的度等局部信息进行匹配的粗化算法，在对原始图粗化过程中发挥结点核值导向性作用，克服以往只能选择随机匹配（RM）算法作为导向匹配算法的缺陷；提出了基于CSHEM和重边匹配（HEM）算法的组合粗化策略，在发挥结点核值的导向性作用的同时，又不至于被过分强调而使粗化图违背结点核值大小均匀分布的原则。基于ISPD98电路测试基准的实验和分析表明，相比无向图剖分软件MeTiS采用的RM和HEM算法的组合粗化策略，提出的策略取得了一定性能的改进。