Супердерево максимального соответствия: различия между версиями
Перейти к навигации
Перейти к поиску
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 22: | Строка 22: | ||
Лемма 1 ([8]). Для любого множества D = | Лемма 1 ([8]). Для любого множества <math>D = \{ T_1, T_2, ..., T_k \} \;</math> корневых неупорядоченных деревьев с уникальными метками листьев, таких, что <math>\Lambda(T_1) = \Lambda(T_2) = ... = \Lambda(T_k) \;</math>, оптимальное решение задачи MASP для D является оптимальным решением задачи MAST для D, и наоборот. | ||
| Строка 56: | Строка 56: | ||
Теорема 8 ([ ]). Пусть дано множество k бинарных деревьев T степени D с n различных меток листьев; их супердерево максимального соответствия может быть найдено за время O((kD)kD+3(2n)k). | Теорема 8 ([ ]). Пусть дано множество k бинарных деревьев T степени D с n различных меток листьев; их супердерево максимального соответствия может быть найдено за время O((kD)kD+3(2n)k). | ||
== Применение == | == Применение == | ||