Дерево максимальной совместимости: различия между версиями

'''Теорема 3 ([2]).'''

'''1. Задача <math>MCT_p \;</math> для корневых деревьев может быть решена за время <math>O(min \{ 3^p kn, 2.27^p + kn^3 \}) \;</math>.'''

'''2. Задача <math>MCT_p \;</math> для некорневых деревьев может быть решена за время <math>O \big( (p + 1) \times min \{ 3^p kn, 2.27^p + kn^3 \} \big) \;</math>.'''

Терм <math>3^p kn \;</math> возникает из-за использования алгоритма, который вначале за время O(kn) локализует множество S из трех листьев, на котором входные деревья конфликтуют, а затем рекурсивным образом вычисляет деревья максимальной совместимости <math>T_1 \;</math>, <math>T_2 \;</math> и <math>T_3 \;</math> для каждого из трех наборов <math>\mathcal{T}_1 \;</math>, <math>\mathcal{T}_2 \;</math> и <math>\mathcal{T}_3 \;</math>, соответственно, полученных посредством удаления принадлежащего S листа из входных деревьев, и затем возвращает <math>T_i \;</math>, такое, что <math>|T_i| \;</math> максимально (для <math>i \in [1, 3] \;</math>). Терм <math>2.27^p + kn^3 \;</math> появляется из-за использования алгоритма, выполняющего редукцию MCT до 3-HITTING SET. Гийемо и Николя получили отрицательный результат при рассмотрении возможности разрешимости MCT с фиксированными параметрами для входных деревьев степени не выше D.

'''Теорема 4 ([7]).'''

 

'''1. MCT является W[1]-полной относительно D.'''

 

'''2. MCT не может быть решена за время <math>O(N^{o(2^{D/2})}) \;</math>, если только не выполняется <math>SNP \subseteq SE \;</math>, где N обозначает длину входных элементов, т.е. N = O(kn).'''