计算机科学 ›› 2006, Vol. 33 ›› Issue (11): 219-221.
• 计算机网络与信息安全 • 上一篇 下一篇
出版日期:
发布日期:
基金资助:
Online:
Published:
摘要： 图同构问题是指对两个图寻找顶点之间的一个一一映射，使得两图的边在该映射下也保持对应关系，该问题得到许多研究者的关注。在一些论文中对图同构问题的复杂性给出了错误的描述，有的给出了多项式时问算法。本文对此进行了讨论，并给出了一些反例来证明其算法的错误。根据图同构国内外目前的研究进展，图同构既未被归入P问题，也未被归入NPC问题，是一个尚未解决的问题，有待进一步研究。
关键词: 图同构 NP问题 P问题 NPC问题 图同构完备
Abstract: The graph isomorphism is to find a bijection between the vertexes of two graphs that preserve the edges. This problem＇has been paid much attention by many researchers. In some papers the complexity of the graph problem has been wrong described, and polyno
Key words: Graph isomorphism, NP problem, P problem, NPC problem, Graph isomorphism complete
. 关于图同构复杂性的分析[J]. 计算机科学, 2006, 33(11): 219-221. https://doi.org/
0 / / 推荐
导出引用管理器 EndNote|Reference Manager|ProCite|BibTeX|RefWorks
链接本文: https://www.jsjkx.com/CN/
https://www.jsjkx.com/CN/Y2006/V33/I11/219
Cited
首页