4501
правка
Дерево максимальной совместимости: различия между версиями
Перейти к навигации
Перейти к поиску
м
Дерево максимальной совместимости (посмотреть исходный код)
Версия от 00:59, 6 декабря 2015
, 6 декабря 2015нет описания правки
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) мНет описания правки |
||
| Строка 42: | Строка 42: | ||
'''Теорема 1 ([5]). Пусть L – множество, содержащее n листьев. Задача MCT для набора из k корневых деревьев с листьями из L, в котором каждое дерево имеет степень не выше d + 1, может быть решена за время <math>O(2^{2kd} n^k) \;</math>. | '''Теорема 1 ([5]).''' Пусть L – множество, содержащее n листьев. Задача MCT для набора из k корневых деревьев с листьями из L, в котором каждое дерево имеет степень не выше d + 1, может быть решена за время <math>O(2^{2kd} n^k) \;</math>. | ||
| Строка 48: | Строка 48: | ||
'''Теорема 2 ([5]). Пусть дан набор из k некорневых деревьев, степени которых не превышают d + 1, с множеством листьев мощности n. Тогда задача MCT может быть решена за время <math>O(2^{2kd} n^{k+1}) \;</math>. | '''Теорема 2 ([5]).''' Пусть дан набор из k некорневых деревьев, степени которых не превышают d + 1, с множеством листьев мощности n. Тогда задача MCT может быть решена за время <math>O(2^{2kd} n^{k+1}) \;</math>. | ||
| Строка 56: | Строка 56: | ||
'''Теорема 3 ([2]).''' | '''Теорема 3 ([2]).''' | ||
1. Задача <math>MCT_p \;</math> для корневых деревьев может быть решена за время <math>O(min \{ 3^p kn, 2.27^p + kn^3 \}) \;</math>. | |||
2. Задача <math>MCT_p \;</math> для некорневых деревьев может быть решена за время <math>O \big( (p + 1) \times min \{ 3^p kn, 2.27^p + kn^3 \} \big) \;</math>. | |||
| Строка 66: | Строка 66: | ||
'''Теорема 4 ([7]).''' | '''Теорема 4 ([7]).''' | ||
1. MCT является W[1]-полной относительно D. | |||
2. MCT не может быть решена за время <math>O(N^{o(2^{D/2})}) \;</math>, если только не выполняется <math>SNP \subseteq SE \;</math>, где N обозначает длину входных элементов, т.е. N = O(kn). | |||
| Строка 78: | Строка 78: | ||
Идея локализации и последующего успешного удаления всех конфликтов между входными деревьями также привела к созданию алгоритмов аппроксимации для ''дополнения'' задачи MCT, обозначаемого CMCT. Пусть L – множество листьев каждого дерева входного набора T. Целью задачи CMCT является выбор наименьшего числа листьев <math>S \subseteq I \;</math>, таких, что набор <math>\{ T_i | (L - S): T_i \in \mathcal{T} \} \;</math> является совместимым. | Идея локализации и последующего успешного удаления всех конфликтов между входными деревьями также привела к созданию алгоритмов аппроксимации для ''дополнения'' задачи MCT, обозначаемого CMCT. Пусть L – множество листьев каждого дерева входного набора T. Целью задачи CMCT является выбор наименьшего числа листьев <math>S \subseteq I \;</math>, таких, что набор <math>\{ T_i | (L - S): T_i \in \mathcal{T} \} \;</math> является совместимым. | ||
''' | |||
Теорема 5 ([6]). Пусть дан набор <math>\mathcal{T} \;</math> из k корневых деревьев с множеством листьев L мощности n. Тогда существует алгоритм 3-аппроксимации задачи MCT с временем исполнения <math>O(k^2 n^2) \;</math>. | '''Теорема 5 ([6]).''' Пусть дан набор <math>\mathcal{T} \;</math> из k корневых деревьев с множеством листьев L мощности n. Тогда существует алгоритм 3-аппроксимации задачи MCT с временем исполнения <math>O(k^2 n^2) \;</math>. | ||
| Строка 85: | Строка 85: | ||
'''Теорема 6 ([1]). Существует алгоритм 3-аппроксимации с временем исполнения <math>O(kn + n^2) \;</math> для решения задачи CMCT на наборе k корневых деревьев с n листьев. | '''Теорема 6 ([1]).''' Существует алгоритм 3-аппроксимации с временем исполнения <math>O(kn + n^2) \;</math> для решения задачи CMCT на наборе k корневых деревьев с n листьев. | ||