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

Хотя задача MASP является NP-полной, существует алгоритм аппроксимации для ее приближенного решения.

Также существуют алгоритмы вычисления MASP с фиксированными параметрами и полиномиальным временем решения. Случай с множеством k бинарных деревьев T с n различных меток листьев рассматривался множеством исследователей. Дженссон и коллеги [8] первыми предложили алгоритм вычисления MAST на T с временем исполнения <math>O(k(2n^2)^{3k^2}) \;</math>. Недавно Гийемо и Берри [5] улучшили это время до <math>O((8n)^k) \;</math>; Хоанг и Сунг [7] снизили его до <math>O((6n)^k) \;</math>, что показано в теореме 7.

Для случая, когда множество k бинарных деревьев T имеют степень D и n различных меток листьев, Хоанг и Сунг [7] предложили следующее решение для нахождения MASP с фиксированными параметрами и полиномиальным временем исполнения.

Задача 2. Пусть D = f T1 ; T2; : ; Tk g – множество корневых неупорядоченных деревьев, в котором каждое дерево Ti имеет уникальные метки листьев, при этом множества меток листьев A(Tj) могут перекрываться. Задача нахождения супердерева максимальной совместимости (MCSP) заключается в построении дерева Q с уникальными метками листьев, с множеством меток листьев A(Q) С ST2D A(Tj), таким, что \A(Q)\ максимально и для каждого Ti 2 D топологическое ограничение поддерева Q0 дерева Q согласно A(Tj) уточняет топологическое ограничение Ti0 согласно Ti; иначе говоря, Ti0 может быть получено путем коллапсирования определенных ребер Qi0.