Premium
Common subgraph isomorphism detection by backtracking search
Author(s) -
Krissinel Evgeny B.,
Henrick Kim
Publication year - 2004
Publication title -
software: practice and experience
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.437
H-Index - 70
eISSN - 1097-024X
pISSN - 0038-0644
DOI - 10.1002/spe.588
Subject(s) - subgraph isomorphism problem , backtracking , induced subgraph isomorphism problem , clique , graph isomorphism , computer science , computational complexity theory , isomorphism (crystallography) , graph , theoretical computer science , representation (politics) , algorithm , combinatorics , mathematics , line graph , voltage graph , chemistry , crystal structure , crystallography , politics , political science , law
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.