Ivan Olmos, Jesus A. Gonzalez, Mauricio Osorio
Inexact graph matching has become an important research area because it is used to find similarities among objects in several real domains such as chemical and biological compounds. Let G and G' be input labeled graphs, we present an algorithm capable to find a graph S of G, where S is isomorphic to G' and the corresponding labels between the vertices and edges of S and G' are not the same (inexact matching). We use a list-code based representation without candidate generation, where a step by step expansion is implemented. The proposed approach is suitable to work with directed and undirected graphs. We conducted a set of experiments in a genome database in order to show the effectiveness of our algorithm. Our experiments show a promissing method to be used with scalable graph matching tools that can be applied to areas such as Machine Learning (ML) and Data Mining (DM).
Subjects: 12. Machine Learning and Discovery; 11. Knowledge Representation
Submitted: Feb 13, 2006