Subgraphs Isomorphism

Raymond JW, Willett P. Maximum common subgraph isomorphism algorithms for the matching of chemical structures. J Comput-Aided Mol Des 2002 16 521-33. 

Ullmann, J.R. An algorithm for subgraph isomorphism. /. Assoc. Comput. Machinery. 1976, 23, 31-42. 

A generalization of the isomorphism problem is the subgraph isomorphism problem. Given two graphs G1 = (V, ) and... 

The situation for the subgraph isomorphism problem is somewhat better understood and somewhat more gloomy. It is possible... 

On trees, not only is the isomorphism problem efficiently solvable, but so is the subgraph isomorphism problem. Edmonds and Matula (29) have discovered an algorithm which will determine whether one tree is isomorphic to a subtree of another in... 

Barrow, H. G. and R. M. Burstall, "Subgraph Isomorphism, Matching Relational Structures, and Maximal Cliques," Information Processing Letters, (4), 83-84 (January 1976). 

The refinement procedure utilises the fact that if some query node Q(X) has another node Q(fV) at some specific distance ) ( and/or angle), and if some database node D(Z) matches with Q(W), then there must also be some node D(Y) at the appropriate distance(s) from D(Z) which matches with Q(X) this is a necessary, but not sufficient, condition for a subgraph isomorphism to be present (except in the limiting case of all the query nodes having been matched, when the condition is both necessary and sufficient). The refinement procedure is called before each possible assignment of a database node to a query node and the matched substructure is increased by one node if, and only if, the condition holds for all nodes W, X, Y and Z. The basic algorithm terminates once a match has been detected or until a mismatch has been confirmed [70] it is easy to extend the algorithm to enable the detection of all matches between a query pattern and a database structure, as is required for applications such as those discussed here. 

In order to conduct a search, the graphs that represent each of the proteins in the PDB must be examined using a subgraph isomorphism algorithm to see if they... 

There are two approaches to solve the subgraph isomorphism problem. The first approach is based on the following two-step procedure ... 

H.G. Barrow, R.M. Burstall, Subgraph Isomorphism, Matching Relational Structures and Maximal Cliques, Information Proc-cesing Letters, 4 (1976) 83-84. 

Cortadella J, Valiente G. A relational view of subgraph isomorphism. In Proc. Fifth Int. Seminar on Relational Methods in Computer Science, Quebec, Canada, 2000. pp. 45-54. 

Substructure Search. Application of subgraph isomorphism" search to chemical structures. This consists of finding a particular arrangement of atoms and bonds as they are embedded in a chemical structure. The arrangement being searched for is termed the query substructure, the structures being searched are termed the candidates, and any particular structure in that set is termed a target structure. If the query substructure is... 

Subgraph isomorphism algorithms can find a snbstrnctnre within a structure. 

---