Inexact Graph Matching: A Case of Study.
Iván Olmos, Jesús A. González, Mauricio Osorio · 2006
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 listcode 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).