Tags

Type your tag names separated by a space and hit enter

A (sub)graph isomorphism algorithm for matching large graphs.
IEEE Trans Pattern Anal Mach Intell. 2004 Oct; 26(10):1367-72.IT

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+Show Affiliations

Cordella LP
Dipartimento di Informatica e Sistemistica, Universitá di Napoli Federico II Via Claudio 21, I-80125 Napoli, Italy. cordel@unina.it
Foggia P
No affiliation info available
Sansone C
No affiliation info available
Vento M
No affiliation info available

MeSH

AlgorithmsArtificial IntelligenceCluster AnalysisComputer GraphicsImage EnhancementImage Interpretation, Computer-AssistedImaging, Three-DimensionalInformation Storage and RetrievalNumerical Analysis, Computer-AssistedPattern Recognition, AutomatedReproducibility of ResultsSensitivity and SpecificitySignal Processing, Computer-AssistedSubtraction Technique

Pub Type(s)

Comparative Study
Evaluation Study
Journal Article
Validation Study

Language

eng

PubMed ID

15641723

Citation

Cordella, Luigi P., et al. "A (sub)graph Isomorphism Algorithm for Matching Large Graphs." IEEE Transactions On Pattern Analysis and Machine Intelligence, vol. 26, no. 10, 2004, pp. 1367-72.
Cordella LP, Foggia P, Sansone C, et al. A (sub)graph isomorphism algorithm for matching large graphs. IEEE Trans Pattern Anal Mach Intell. 2004;26(10):1367-72.
Cordella, L. P., Foggia, P., Sansone, C., & Vento, M. (2004). A (sub)graph isomorphism algorithm for matching large graphs. IEEE Transactions On Pattern Analysis and Machine Intelligence, 26(10), 1367-72.
Cordella LP, et al. A (sub)graph Isomorphism Algorithm for Matching Large Graphs. IEEE Trans Pattern Anal Mach Intell. 2004;26(10):1367-72. PubMed PMID: 15641723.
* Article titles in AMA citation format should be in sentence-case
TY - JOUR T1 - A (sub)graph isomorphism algorithm for matching large graphs. AU - Cordella,Luigi P, AU - Foggia,Pasquale, AU - Sansone,Carlo, AU - Vento,Mario, PY - 2005/1/12/pubmed PY - 2005/2/11/medline PY - 2005/1/12/entrez SP - 1367 EP - 72 JF - IEEE transactions on pattern analysis and machine intelligence JO - IEEE Trans Pattern Anal Mach Intell VL - 26 IS - 10 N2 - 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. SN - 0162-8828 UR - https://www.unboundmedicine.com/medline/citation/15641723/A__sub_graph_isomorphism_algorithm_for_matching_large_graphs_ DB - PRIME DP - Unbound Medicine ER -