A new algorithm for error-tolerant subgraph isomorphism detection

1 May 1998

journal article
Published by Institute of Electrical and Electronics Engineers (IEEE)

Vol. 20 (5) , 493-504
https://doi.org/10.1109/34.682179

Abstract

We propose a new algorithm for error-correcting subgraph isomorphism detection from a set of model graphs to an unknown input graph. The algorithm is based on a compact representation of the model graphs. This representation is derived from the set of model graphs in an off-line preprocessing step. The main advantage of the proposed representation is that common subgraphs of different model graphs are represented only once. Therefore, at run time, given an unknown input graph, the computational effort of matching the common subgraphs for each model graph onto the input graph is done only once. Consequently, the new algorithm is only sublinearly dependent on the number of model graphs. Furthermore, the new algorithm can be combined with a future cost estimation method that greatly improves its run-time performance.

Keywords

This publication has 23 references indexed in Scilit:

Organizing large structural modelbases
Published by Institute of Electrical and Electronics Engineers (IEEE) ,1995
Analysis of scenes containing multiple non-polyhedral 3D objects
Published by Springer Nature ,1995
Inexact matching using neural networks
Published by Elsevier ,1994
PROBABILISTIC RELAXATION FOR MATCHING OF SYMBOLIC STRUCTURES
Published by World Scientific Pub Co Pte Ltd ,1993
TRANSLATION-, ROTATION- AND SCALE- INVARIANT RECOGNITION OF HAND-DRAWN SYMBOLS IN SCHEMATIC DIAGRAMS
International Journal of Pattern Recognition and Artificial Intelligence, 1990
A graph distance measure for image analysis
IEEE Transactions on Systems, Man, and Cybernetics, 1984
A distance measure between attributed relational graphs for pattern recognition
IEEE Transactions on Systems, Man, and Cybernetics, 1983
Organization of Relational Models for Scene Analysis
Published by Institute of Electrical and Electronics Engineers (IEEE) ,1982
Rete: A fast algorithm for the many pattern/many object pattern match problem
Artificial Intelligence, 1982
Structural Descriptions and Inexact Matching
Published by Institute of Electrical and Electronics Engineers (IEEE) ,1981