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

== Основные результаты ==

Было показано, что задача MCT является NP-полной для 6 деревьев ([9]) и для 2 деревьев [10]. NP-полнота появляется, когда по меньшей мере одно из входных деревьев имеет неограниченную степень. Для случая двух деревьев с ограниченной степенью Хайн и коллеги упоминают алгоритм с полиномиальным временем исполнения, основанный на выравнивании деревьев [10]. Ганапати и Уорноу [5] предложили экспоненциальный алгоритм для решения задачи MCT в общем виде. Они показали, как для двух деревьев <math>T_1, T_2 \;</math> вычислить бинарное дерево MCT для любой пары поддеревьев <math>(S_1 \in T_1, S_2 \in T_2) \;</math> при помощи динамических алгоритмов. Поддеревья, корни которых имеют высокую степень, обрабатываются путем рассмотрения каждого возможного разбиения потомков корня на два множества. Из-за этого в оценке сложности появляется экспоненциальный терм относительно d – максимальной степени вершин входных деревьев. Если имеются k входных деревьев, то рассматриваются кортежи из k поддеревьев и производится подобное же разбиение потомков корневых вершин на два множества для k поддеревьев. Следовательно, сложность по-прежнему является экспоненциальной относительно k.