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

Далее рассматривается задача построения тонкослойной сети N, согласующейся с максимальным количеством корневых триплетов из T для любого (не обязательно плотного) множества T. Поскольку из теоремы 2 следует, что эта задача является NP-полной, были исследованы алгоритмы аппроксимации для ее приближенного решения. Алгоритм называется k-аппроксимируемым, если он всегда возвращает тонкослойную сеть N, такую, что N(T)/|T| > k, где N(T) – количество корневых триплетов в T, согласующихся с N.

Теорема 3. Пусть дано множество корневых триплетов T. Не существует алгоритма аппроксимации, результатом работы которого является тонкослойная сеть N, такая, что N(T)/|T| > 0.4883.

Теорема 4. Пусть дано множество корневых триплетов T. Существует алгоритм аппроксимации, результатом работы которого является тонкослойная сеть N, такая, что N(T)/|T| > 5/12. Время работы алгоритма составляет О(\А(Т)\\Т\Ъ).