A (sub)graph isomorphism algorithm for matching large graphs
A (sub)graph isomorphism algorithm for matching large graphs
复制标题
DOI：
10.1109/tpami.2004.75
复制
发表时间：
2004-10-01
影响因子：
23.6
通讯作者：
Vento, M
中科院分区：
文献类型：
--
作者：
Cordella, LP;Foggia, P;Vento, M
提出了一种适合处理大图的图同构和子图同构算法。该算法的第一个版本已经在之前的一篇论文中提出，在那里我们检查了它对中小型图同构的性能。本文对算法进行了改进，以降低其空间复杂度，并在大图上获得更好的性能；详细分析了它的特点，并特别参考了时间和内存要求。本文给出了在一个公开可用的合成图形数据库上进行的测试结果，以及在处理技术图纸的实际应用程序上进行的测试结果，证实了该方法的有效性，特别是在处理大型图形时。
We present an algorithm for graph isomorphism and subgraph isomorphism suited for dealing with large graphs. A first version of the algorithm has been presented in a previous paper, where we examined its performance for the isomorphism of small and medium size graphs. The algorithm is improved here to reduce its spatial complexity and to achieve a better performance on large graphs; its features are analyzed in detail with special reference to time and memory requirements. The results of a testing performed on a publicly available database of synthetically generated graphs and on graphs relative to a real application dealing with technical drawings are presented, confirming the effectiveness of the approach, especially when working with large graphs.