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.
A (Sub)Graph Isomorphism Algorithm for Matching Large Graphs / Cordella, LUIGI PIETRO; Foggia, Pasquale; Sansone, Carlo; M., Vento. - In: IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE. - ISSN 0162-8828. - STAMPA. - 26:10(2004), pp. 1367-1372. [10.1109/TPAMI.2004.75]
A (Sub)Graph Isomorphism Algorithm for Matching Large Graphs
CORDELLA, LUIGI PIETRO;FOGGIA, PASQUALE;SANSONE, CARLO;
2004
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.File | Dimensione | Formato | |
---|---|---|---|
t-pami04.pdf
non disponibili
Tipologia:
Documento in Post-print
Licenza:
Accesso privato/ristretto
Dimensione
549.31 kB
Formato
Adobe PDF
|
549.31 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.