This paper presents an algorithm for the computation of the maximum common subgraph (MCS) between two directed, acyclic graphs with attributes. The core of the contribution resides in the modularity of the proposed algorithm which allows different heuristic techniques to be plugged in, depending on the application domain. Implemented heuristics for robust graph matching with respect to graph structural noise are discussed. As example of its effectiveness, the algortihm is applied to the problem of 3D shape similarity evaluation through structural shape descriptors.
From exact to approximate maximum common subgraph
Marini S;Spagnuolo M;Falcidieno B
2005
Abstract
This paper presents an algorithm for the computation of the maximum common subgraph (MCS) between two directed, acyclic graphs with attributes. The core of the contribution resides in the modularity of the proposed algorithm which allows different heuristic techniques to be plugged in, depending on the application domain. Implemented heuristics for robust graph matching with respect to graph structural noise are discussed. As example of its effectiveness, the algortihm is applied to the problem of 3D shape similarity evaluation through structural shape descriptors.File in questo prodotto:
| File | Dimensione | Formato | |
|---|---|---|---|
|
prod_183009-doc_30280.pdf
solo utenti autorizzati
Descrizione: commonSubgraph
Dimensione
180.18 kB
Formato
Adobe PDF
|
180.18 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
|
prod_183009-doc_30918.pdf
solo utenti autorizzati
Descrizione: FrontMatter
Dimensione
125.06 kB
Formato
Adobe PDF
|
125.06 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.
