A (sub)graph isomorphism algorithm for matching large graphs |
| |
Authors: | Cordella Luigi P Foggia Pasquale Sansone Carlo Vento Mario |
| |
Affiliation: | Dipt. di Inf. e Sistemistica, Univ. di Napoli "Federico II", Italy; |
| |
Abstract: | 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. |
| |
Keywords: | |
本文献已被 PubMed 等数据库收录! |
|