一种对称无向图的同构判定算法

摘要：

文章在电路模拟法的基础上提出了一种对称无向图的同构判定算法.电路模拟法对随机图的同构判定问题非常有效,但是对于处理对称度较高的图,判定效率明显降低甚至失效.该文提出的算法针对对称无向图的特性,在电路模拟法的基础上结合Dijkstra算法,综合得到顶点属性和最短距离序列来搜索顶点之间的映射关系,能够有效判定这类图的同构问题.

关键词：对称无向图、图同构、电路模拟法、Dijkstra算法、距离序列

所属期刊栏目：44

分类号：TP301.6(计算技术、计算机技术)

资助基金：国家自然科学基金资助项目61474001

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

页数：共5页

页码：332-336