logo标签列表

子图同构检测的算法

algorithmgraphsubgraph
7

子图同构是一个NP完全问题。目前最广泛使用的算法是Ullman提出的算法。

有人能用通俗易懂的语言解释一下这个算法吗？我读了他写的论文，但没怎么理解。

还有哪些算法可以解决这个问题？

我正在做一个图像处理项目。

@Hamish：什么样的学校/大学会把解决NP完全问题作为家庭作业？我可能会加入它 :) - Bruce
研究生课程中的教授们喜欢通过在作业集中提出一两个疯狂的问题来淘汰和招募天才。 - Hamish Grubijan
@Hamish：这对我来说是个新闻。我仍然是一个本科生，绝对不是天才 :) - Bruce
2
NP完全并不意味着问题无法解决；它只是意味着没有已知的精确算法，随着输入规模的增大呈多项式级别扩展。通常仍然可以找到近似算法，并且通常可以解决相当一部分小规模输入大小的问题。（例如，旅行商问题可以解决数万个节点。） - ShreevatsaR
我认为目前该领域最新的进展是来自SIGMOD 2013的Turboiso：面向大型图数据库中超快速和稳健的子图同构搜索。作者还在VLDB 2012上发表了一篇调查论文，介绍了现有算法。 - lgylym
显示剩余2条评论
2个回答
3
2

这篇博客文章试图概述这个算法。原始介绍很难阅读，因为它呈现的算法就像你在70年代的计算机上编写一样。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接