A (sub)graph isomorphism algorithm for matching large graphs
Top Cited Papers
- 16 August 2004
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 26 (10) , 1367-1372
- https://doi.org/10.1109/tpami.2004.75
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
This publication has 16 references indexed in Scilit:
- A decision tree approach to graph and subgraph isomorphism detectionPattern Recognition, 1999
- A Minimal Line Property Preserving Representation of Line ImagesComputing, 1999
- Performance evaluation of the VF graph matching algorithmPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1999
- Subgraph Transformations for the Inexact Matching of Attributed Relational GraphsPublished by Springer Nature ,1998
- Structural matching in computer vision using probabilistic relaxationPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1995
- A Metric for Comparing Relational DescriptionsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1985
- Subgraph error-correcting isomorphisms for syntactic pattern recognitionIEEE Transactions on Systems, Man, and Cybernetics, 1983
- Isomorphism of graphs of bounded valence can be tested in polynomial timeJournal of Computer and System Sciences, 1982
- Principles of Artificial IntelligencePublished by Springer Nature ,1982
- An Algorithm for Subgraph IsomorphismJournal of the ACM, 1976