4501
правка
Поддерево максимального соответствия (для трех или более деревьев): различия между версиями
Перейти к навигации
Перейти к поиску
м
Поддерево максимального соответствия (для трех или более деревьев) (посмотреть исходный код)
Версия от 22:56, 24 сентября 2015
, 24 сентября 2015→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 14: | Строка 14: | ||
== Основные результаты == | == Основные результаты == | ||
В общем случае задача k-MAST является NP-полной для k > | В общем случае задача k-MAST является NP-полной для <math>k \ge 3 \;</math> [1]. В предположении, что степень хотя бы одного из деревьев ограничена, Фарах и коллеги предложили алгоритм, на базе которого была сформулирована следующая теорема: | ||
Теорема 1. Если степень деревьев в кортеже T = (T1..: ; Tk) ограничена числом d, то значение k-MAST(T) может быть вычислено за время O(kn3 + nd). | '''Теорема 1.''' Если степень деревьев в кортеже T = (T1..: ; Tk) ограничена числом d, то значение k-MAST(T) может быть вычислено за время O(kn3 + nd). | ||
В последующем изложении будем считать, что задача огранивается нахождением мощности максимального множества соответствия, а не самого множества. Можно довольно простым способом расширить этот алгоритм до алгоритма, вычисляющего множество соответствия (и, следовательно, поддерево соответствия) в тех же временных рамках. | В последующем изложении будем считать, что задача огранивается нахождением мощности максимального множества соответствия, а не самого множества. Можно довольно простым способом расширить этот алгоритм до алгоритма, вычисляющего множество соответствия (и, следовательно, поддерево соответствия) в тех же временных рамках. | ||
| Строка 68: | Строка 68: | ||
Наконец, остается продемонстрировать, что после того, как lca-кортежи и отношение строгого доминирования предварительно вычислены, вычисление всех ненулевых значений mast может быть выполнено за время O(nd). Это производится при помощи генерации всех возможных клик для всех значений G(vE). Используя тот факт, что степень по меньшей мере одного дерева ограничена d, можно показать, что все клики могут быть сгенерированы за время O(J2}<d (")) = O(d3(ne/d)d) и что их имеется O(d(ne/d)d) штук [ ]. | Наконец, остается продемонстрировать, что после того, как lca-кортежи и отношение строгого доминирования предварительно вычислены, вычисление всех ненулевых значений mast может быть выполнено за время O(nd). Это производится при помощи генерации всех возможных клик для всех значений G(vE). Используя тот факт, что степень по меньшей мере одного дерева ограничена d, можно показать, что все клики могут быть сгенерированы за время O(J2}<d (")) = O(d3(ne/d)d) и что их имеется O(d(ne/d)d) штук [ ]. | ||
== Применение == | == Применение == | ||