4446
правок
Поддерево максимального соответствия (для трех или более деревьев): различия между версиями
Перейти к навигации
Перейти к поиску
м
Поддерево максимального соответствия (для трех или более деревьев) (посмотреть исходный код)
Версия от 22:56, 24 сентября 2015
, 24 сентября 2015нет описания правки
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) мНет описания правки |
||
| Строка 17: | Строка 17: | ||
'''Теорема 1.''' Если степень деревьев в кортеже T = ( | '''Теорема 1.''' Если степень деревьев в кортеже <math>\overrightarrow{T} = (T^1, ..., T^k) \;</math> ограничена числом d, то значение k-MAST(T) может быть вычислено за время <math>O(kn^3 + n^d) \;</math>. | ||
В последующем изложении будем считать, что задача огранивается нахождением мощности максимального множества соответствия, а не самого множества. Можно довольно простым способом расширить этот алгоритм до алгоритма, вычисляющего множество соответствия (и, следовательно, поддерево соответствия) в тех же временных рамках. | В последующем изложении будем считать, что задача огранивается нахождением мощности максимального множества соответствия, а не самого множества. Можно довольно простым способом расширить этот алгоритм до алгоритма, вычисляющего множество соответствия (и, следовательно, поддерево соответствия) в тех же временных рамках. | ||