关于图同构复杂性的分析

• 作者: 戴琼 谭建龙 邹潇湘
• 来源期刊: 计算机科学
• 学科: 工学
• 关键词: 图同构 NP问题 P问题 NPC问题 图同构完备
• 年，卷（期）: 2006,（11）
• 所属期刊栏目: 人工智能及图像处理技术
• 页码范围: 219-221
• 页数: 3页
• 分类号: TP3
• 字数: 3356字
• 语种: 中文
• DOI: 10.3969/j.issn.1002-137X.2006.11.063

摘要

图同构问题是指对两个图寻找顶点之间的一个一一映射,使得两图的边在该映射下也保持对应关系,该问题得到许多研究者的关注.在一些论文中对图同构问题的复杂性给出了错误的描述,有的给出了多项式时间算法.本文对此进行了讨论,并给出了一些反例来证明其算法的错误.根据图同构国内外目前的研究进展,图同构既未被归入P问题,也未被归入NPC问题,是一个尚未解决的问题,有待进一步研究.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	谭建龙	中国科学院计算技术研究所	43	444	11.0	19.0
2	戴琼	中国科学院软件研究所	7	65	3.0	7.0
3	邹潇湘		3	40	3.0	3.0