(ref.doc)spe34-6

Software Practice & Experience
May 2004, Vol 34, No 6

Common subgraph isomorphism detection by backtracking search
Evgeny B. Krissinel and Kim Henrick

Graph theory offers a convenient and highly attractive approach to
various task of pattern recognition. Provided there is a graph
representation of the object in question, the recognition procedure is
reduced to the problem of common subgraph isomorphism (CSI).
Complexity of this problem shows combinatorial dependence on the size
of the input graphs, which in many practical cases makes the approach
computationnally intractable. Among the optimal algorithms for CSI,
the leading place in practice belongs to algorithms based on maximal
clique detection in the association graph.