无向图的层次化谱分析同构判定算法

摘要：

针对无向图同构的判定问题, 一种层次化的基于谱分析的同构判定算法. 比较两图的顶点数、边数以及度数序列对图进行预同构判定; 然后对具有唯一 Fiedler 向量的图通过层次化的谱分析算法进行再次同构判定. 与最具代表性的同构判定算法 Nauty 相比, 随着判定图的规模增大, 该算法对于规则网格图和固定度数图具有更高的同构判定效率.

关键词：图同构、谱分析、Fiedler向量、层次化方法

所属期刊栏目：27

分类号：TP391.71(计算技术、计算机技术)

资助基金：国家自然科学基金91330201, 61125401, 61376040, 61474026;国家"十二五"科技重大专项2011ZX01035-001-001-003;上海市教育发展基金会晨光计划

在线出版日期：2015-11-25（万方平台首次上网日期，不代表论文的发表时间）

页数：共8页

页码：2169-2176