首页 | 本学科首页   官方微博 | 高级检索  
     检索      

基于路径信息比较的图同构新算法
引用本文:何洁月,沈斌.基于路径信息比较的图同构新算法[J].东南大学学报(自然科学版),2015,45(2):236-240.
作者姓名:何洁月  沈斌
作者单位:1. 东南大学计算机科学与工程学院,南京210096;东南大学计算机网络和信息集成教育部重点实验室,南京210096
2. 东南大学计算机科学与工程学院,南京,210096
基金项目:江苏省自然科学基金资助项目
摘    要:为了在多项式时间内解决图同构问题,首先证明了2个同构图相等长度的路径信息必相同是图同构判定更为严格的必要条件.然后,根据此条件,提出了一种基于路径信息比较的图同构PIC算法.该算法依次比较各长度的路径信息,对邻接矩阵进行调整,从而实现了2个图的快速同构判定.为了减少路径信息的计算时间,引入Hash函数对PIC算法进行改进,从而得到了HPIC算法.实验结果表明,所提的2种算法均能够正确判定1×104对不同类型、不同大小的随机图是否同构,并且图同构判定的时间复杂度明显降低.HPIC算法的运行速度快于PIC算法;这2种算法在时间性能方面均优于CS算法,略劣于Nauty算法;但对于规则2维网孔图,Nauty算法失效,所提的2种算法则仍能快速进行图同构判定.

关 键 词:图同构  幂阶比较  大规模图  路径信息比较

Novel graph isomorphism algorithm based on path information comparison
He Jieyue , Shen Bin.Novel graph isomorphism algorithm based on path information comparison[J].Journal of Southeast University(Natural Science Edition),2015,45(2):236-240.
Authors:He Jieyue  Shen Bin
Abstract:
Keywords:graph isomorphism  matrix power comparison  large graph  path information comparison
本文献已被 CNKI 万方数据 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号