2005 | OriginalPaper | Chapter
From Exact to Approximate Maximum Common Subgraph
Authors : Simone Marini, Michela Spagnuolo, Bianca Falcidieno
Published in: Graph-Based Representations in Pattern Recognition
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
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 algorithm is applied to the problem of 3D shape similarity evaluation through structural shape descriptors.