Algorithm Ullmann

Fig. 12.4 Illustration of the operation of the Ullmann algorithm using a 4-atom substructure and a 6-atom molecule. The proposed match is shown in the bottom figure, together with the relevant matrices used in the calculation...

The basis of the Ullmann algorithm is a refinement heuristic that is applied during the backtrack phase whenever a query... 

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

The performance of the original backtracking algorithm can be further improved by pruning-off fruitless branches of a search tree as early as possible. One technique for achieving this was introduced into a backtracking match algorithm by Ullmann in 1976 [16]. 

Ullmann J R 1976. An Algorithm for Subgraph Isomorphism. Journal of the Association for Computing Machinery 23 31-42. 

A subgraph isomorphism algorithm published by Ullmann in 1976 also contains a refinement step, which is essentially an application of relaxation. 

---