Common subgraph isomorphism detection by backtracking search

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