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

• 作者: 曾璇 杨帆 谢敏
• 来源期刊: 计算机辅助设计与图形学学报
• 学科: 工学
• 关键词: 图同构 谱分析 Fiedler向量 层次化方法
• 年，卷（期）: 2015,（11）
• 所属期刊栏目: VLSI设计与测试及电子设计自动化
• 页码范围: 2169-2176
• 页数: 8页
• 分类号: TP391.71
• 字数: 6408字
• 语种: 中文

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	杨帆	复旦大学专用集成电路与系统国家重点实验室	64	322	10.0	16.0
2	曾璇	复旦大学专用集成电路与系统国家重点实验室	34	66	4.0	6.0
3	谢敏	复旦大学专用集成电路与系统国家重点实验室	2	4	1.0	2.0