A decision tree approach to graph and subgraph isomorphism detection
作者:
Highlights:
•
摘要
A new approach to the problem of graph and subgraph isomorphism detection from 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 preprocessing, the computational complexity of the new graph algorithm is only polynomial in the number of input graph vertices. In particular, it is independent of the number of model graphs and the number of edges in any of the graphs. However, the decision tree is of exponential size. Several pruning techniques which aim at reducing the size of the decision tree are presented. A computational complexity analysis of the new method is given and its behavior is studied in a number of practical experiments with randomly generated graphs.
论文关键词:Graph isomorphism,Subgraph isomorphism,Tree search,Decision tree,Indexing
论文评审过程:Received 17 February 1997, Revised 14 October 1998, Available online 7 June 2001.
论文官网地址:https://doi.org/10.1016/S0031-3203(98)90142-X