2004/08/16 by L.P. Cordella, Pasquale Foggia, Carlo Sansone +1 · 7 citations
Computer Science · Mathematics · #Graph Theory and Algorithms #Data Management and Algorithms #Advanced Database Systems and Queries #Subgraph isomorphism problem #Graph isomorphism #Induced subgraph isomorphism problem #Computer science #Maximal independent set #Cograph #Algorithm #Isomorphism (crystallography) #Chordal graph #Matching (statistics) #Pathwidth #Indifference graph #Time complexity #Graph #Theoretical computer science #Mathematics #Line graph
paper · doi:10.1109/tpami.2004.75
openalex publication_date 2004/08/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/04
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.