Common subgraph isomorphism detection by backtracking search

Abstract

Abstract Graph theory offers a convenient and highly attractive approach to various tasks of pattern recognition. Provided there is a graph representation of the object in question (e.g. a chemical structure or protein fold), the recognition procedure is reduced to the problem of common subgraph isomorphism (CSI). Complexity of this problem shows combinatorial dependence on the size of input graphs, which in many practical cases makes the approach computationally intractable. Among the optimal algorithms for CSI, the leading place in practice belongs to algorithms based on maximal clique detection in the association graph. Backtracking algorithms for CSI, first developed two decades ago, are rarely used. We propose an improved backtracking algorithm for CSI, which differs from its predecessors by better search strategy and is therefore more efficient. We found that the new algorithm outperforms the traditional maximal clique approach by orders of magnitude in computational time. Copyright © 2004 John Wiley & Sons, Ltd.