Graph decomposition
We also use a divide-and-conquer graph decomposition approach for pruning vertices. For every graph part i and vertex u ∈ Vi we consider induced subgraphs Gu = (Vu, Eu) in turn, where Vu = u ∪ V\Vi. Application of the clique-bounds DEE technique to graphs Gu is very effective since one of the graph parts, Giu MathType@MTEF@5@5@+=feaafiart1ev1aaatCvAUfKttLearuWrP9MDH5MBPbIqV92AaeXatLxBI9gBaebbnrfifHhDYfgasaacH8akY=wiFfYdH8Gipec8Eeeu0xXdbba9frFj0=OqFfea0dXdd9vqai=hGuQ8kuc9pgc9s8qqaq=dirpe0xb9q8qiLsFr0=vr0=vr0dc8meaabaqaciaacaGaaeqabaqabeGadaaakeaacqWGhbWrdaqhaaWcbaGaemyAaKgabaGaemyDauhaaaaa@30BE@ contains only one vertex, u, and all the F and F* values that need to be recomputed for the new graph Gu are greatly constrained. The process of updating the F and F* values is efficient as the changes are localized to one part in the graph. Importantly, the best known clique value C* remains intact, since the clique of that larger value exists in the original graph and can be used for the decomposed one, helping to eliminate vertices. For some of the vertices u, iterative application of the DEE criterion and re-computation of the F and F* values causes Gu to become disconnected, implying that vertex u cannot be part of the optimal alignment. Such a vertex u is marked for deletion, and that information is propagated to all subsequently considered induced subgraphs, further constraining the corresponding F and F* values and helping to eliminate other vertices in turn.