Fig. 11
From: Automated design of dynamic programming schemes for RNA folding with pseudoknots
Example of two tree decompositions of the same width, yielding different complexities. The decomposition on the left has \(w_\boxslash =0\), \(w_\boxtimes =4\) and \(w'=4\), which gives a complexity of \(O(n^5)\) (Theorem 4). On the other hand, the decomposition on the right has \(w_\boxslash =4\), \(w_\boxtimes =0\) and \(w'=3\), which yields \(O(n^4)\)