Isomorphism algorithms

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. 

To obtain an effective algorithm for substructure searching the factorial degree of the brute force algorithm has to be drastically deaeased. In the next sections we discuss several approaches where combination leads to a much more effective and apphcable approach for substructure searching. In the process of searching the isomorphism between Gq and a substructure of Gx, the partial mappings Gq —> Gj can be used as well. In these cases, not all atoms from Gq are mapped and, for those which are not, the array value Mj is set to 0. 

In many real-world applications, the isomorphism wotild be found before all 16 mappings were checked. For the example from Figure 6-3, many algorithms would find the isomorphism at the fourth mapping following the leftmost path in the search tree the bold line in Figure 6-4) ... 

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. 

McK98] B.D. McKay, Isomorph-free exhaustive generation, Journal of Algorithms 26 (1998) 306-324. 

The most successful algorithms for general graph isomorphism use the backtrack approach (as a fall-back method) in combination... 

In contrast to the isomorphism problem for general graphs, the isomorphism problem for trees is relatively easy. Any tree with n vertices has exactly n-1 edges. We shall describe an algorithm for constructing, in 0(n) time, a code for any tree, such that two trees are isomorphic if and only if they have... 

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

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. 

---