Дерево максимальной совместимости: различия между версиями

Перейти к навигации Перейти к поиску
м
Строка 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>.'''




Теорема 5 ([6]). Пусть дан набор T из k корневых деревьев с множеством листьев L мощности n. Тогда существует алгоритм 3-аппроксимации задачи MCT с временем исполнения O(k2n2).
Время исполнения этого алгоритма позднее было улучшено:
Время исполнения этого алгоритма позднее было улучшено:




Теорема 6 ([1]). Существует алгоритм 3-аппроксимации с временем исполнения O(kn + n2) для решения задачи CMCT на наборе k корневых деревьев с n листьев.
'''Теорема 6 ([1]). Существует алгоритм 3-аппроксимации с временем исполнения <math>O(kn + n^2) \;</math> для решения задачи CMCT на наборе k корневых деревьев с n листьев.'''
 
 
Отметим, что достижимый порог аппроксимации для CMCT не меняется в зависимости от того, рассматриваются ли корневые или некорневые деревья [1].
Отметим, что достижимый порог аппроксимации для CMCT не меняется в зависимости от того, рассматриваются ли корневые или некорневые деревья [1].


4501

правка

Навигация