title: A (sub)graph isomorphism algorithm for matching large graphs.
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.
authors.affiliation: Dipartimento di Informatica e Sistemistica, Universitá di Napoli Federico II Via Claudio 21, I-80125 Napoli, Italy. cordel@unina.it
authors.forename: Luigi P
authors.initials: LP
authors.lastname: Cordella
authors.forename: Pasquale
authors.initials: P
authors.lastname: Foggia
authors.forename: Carlo
authors.initials: C
authors.lastname: Sansone
authors.forename: Mario
authors.initials: M
authors.lastname: Vento
mesh_terms: D000465:Algorithms; D001185:Artificial Intelligence; D016000:Cluster Analysis; D003196:Computer Graphics; D007089:Image Enhancement / Q000379:methods*; D007090:Image Interpretation, Computer-Assisted / Q000379:methods*; D021621:Imaging, Three-Dimensional / Q000379:methods; D016247:Information Storage and Retrieval / Q000379:methods; D009716:Numerical Analysis, Computer-Assisted; D010363:Pattern Recognition, Automated / Q000379:methods*; D015203:Reproducibility of Results; D012680:Sensitivity and Specificity; D012815:Signal Processing, Computer-Assisted; D013382:Subtraction Technique