A decision tree approach to graph and subgraph isomorphism detection

A new approach to the problem of graph and subgraph isomorphism detection f rom an input graph to a database of model graphs is proposed in this paper. It is based on a preprocessing step in which the model graphs are used to create a decision tree. At run time, subgraph isomorphisms are detected by means of decision tree traversal. If we neglect the time needed for preproc essing, the computational complexity of the new graph algorithm is only pol ynomial in the number of input graph vertices. In particular, it is indepen dent of the number of model graphs and the number of edges in any of the gr aphs. However, the decision tree is of exponential size. Several pruning te chniques which aim at reducing the size of the decision tree are presented. A computational complexity analysis of the new method is given and its beh avior is studied in a number of practical experiments with randomly generat ed graphs. (C) 1999 Pattern Recognition Society. Published by Elsevier Scie nce Ltd. All rights reserved.