Subgraph-isomorphism

Given two graphs Gi and G2, if there exists a subgraph of order k of Gi isomorphic to a subgraph 5 of G2, the pair of isomorphic subgraphs S, S ) is called a common subgraph of order k of Gi and G2. A common subgraph is maximal if there is no common... 

The presence or absence of isomorphism for a pair of graphs is determined by an isomorphism algorithm. Specifically, graph isomorphism, subgraph... 

For database handling it is necessary to compare existing database entries with new ones. Consequently, database registration and retrieval are dependent on isomorphism algorithms which compare two graphs or structure diagrams to determine whether subgraphs are identical or not. 

Gq is a substructure of Gp (i.e., Gq is isomorphic with a subgraph of Gp) if and only if all the atoms of Gq can be mapped onto a subset of atoms of Gp in such a way that the bonds of Gq map the corresponding bonds which connect the mapped atoms fi om Gp Each mapping between Gq and Gxcan be considered as a function... 

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

Here A is a single entry subgraph with entry node and a self-loop back to n. We now add a single entry subgraph A graph isomorphic to A and connect A to n, , the entry of A. There are two possibilities. If node m in A was connected to, then the corresponding node m in A can be connected either back to the entry node of A or A or to the entry node n of A. ... 

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). 

J. Huang, W. Wang and J. Prins, Efficient mining of frequent subgraphs in the presence of isomorphism, in Proceedings of the 3rd IEEE International. Conference on Data Mining (ICDM), IEEE Press, Piscataway, NJ, 2004. 

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. 

---