Backtracking Algorithm

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. 

Figure 6-3. Search tree of mappings obtained by applying the backtracking algorithm for the pair of structures Cq and Qt (see the graphs in Figure 6-2). Array (M, M2, Mj, M4) denotes the mapping 1 —> M, 2 —> M2, 3 —> M3, 4 —> M4.

The depth-first search algorithm the backtracking algorithm, respectively) has an exponential order of computational complexity CC [11] CC = 0(b ). The ex-... 

In the worst case, the backtracking algorithm will form a search tree of depth n, where n is the number of atoms in the query graph. Also, in this case a separate sub-tree search process for each atom of the target graph will be initiated. That is why the linear multiplier m is apphed to Eq. (7). 

The backtracking algorithm is the core part of every software system that performs substructure searching. There are other approaches which have been applied both as alternatives to the backtracking algorithm or (most usually) in combination with it. Section 6.3.3 describes the approaches used for the optimization of the... 

The optimization of the backtracking algorithm usually consists of an application of several heuristics which reduce the number of candidate atoms for mapping from Gq to Gj. These heuristics are based on local properties of the atoms such as atom types, number of bonds, bond orders, and ring membership. According to these properties the atoms in Gq and Gj are separated into different classes. This step is known in the literature as partitioning [13]. Table 6.1 illustrates the process of partitioning. 

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

Construction of large combinatorial libraries by use of real reactions and a heuristic backtracking algorithm... 

---