Поддерево максимального соответствия (для трех или более деревьев): различия между версиями

Наконец, остается продемонстрировать, что после того, как lca-кортежи и отношение строгого доминирования предварительно вычислены, вычисление всех ненулевых значений mast может быть выполнено за время <math>O(n^d) \;</math>. Это производится при помощи генерации всех возможных клик для всех значений <math>G(\overrightarrow{v}) \;</math>. Используя тот факт, что степень по меньшей мере одного дерева ограничена <math>d \;</math>, можно показать, что все клики могут быть сгенерированы за время <math>O \bigg( \sum_{l \le d} \binom{n}{l}) = O(d^3(ne/d)^d \bigg) \;</math> и что их имеется <math>O(d(ne/d)^d) \;</math> штук [6].