Tree-pruning algorithms

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

The combination of the new methods for optimizing and pruning search trees described above, and the backtracking technique, makes the Chen-Robien algorithm a very fast MCSS algorithm. It has become a central mainstay of several other commands within the CSEARCH-NMR database system [69]. 

The backtracking algorithm organizes the search space as a tree where each node corresponds to the application of an operator. At each application, the consistency of the partial structure is evaluated. If consistent, the next operator is applied and the process continues. If inconsistent, this node and attached branches are pruned from the search tree and the algorithm backtracks to the previous node. 

---