Дерево максимальной совместимости: различия между версиями
Перейти к навигации
Перейти к поиску
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 77: | Строка 77: | ||
Идея локализации и последующего успешного удаления всех конфликтов между входными деревьями также привела к созданию алгоритмов аппроксимации для ''дополнения'' задачи 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>.''' | |||
Время исполнения этого алгоритма позднее было улучшено: | Время исполнения этого алгоритма позднее было улучшено: | ||
Теорема 6 ([1]). Существует алгоритм 3-аппроксимации с временем исполнения O(kn + | '''Теорема 6 ([1]). Существует алгоритм 3-аппроксимации с временем исполнения <math>O(kn + n^2) \;</math> для решения задачи CMCT на наборе k корневых деревьев с n листьев.''' | ||
Отметим, что достижимый порог аппроксимации для CMCT не меняется в зависимости от того, рассматриваются ли корневые или некорневые деревья [1]. | Отметим, что достижимый порог аппроксимации для CMCT не меняется в зависимости от того, рассматриваются ли корневые или некорневые деревья [1]. | ||