4551
правка
Остовное дерево с максимальным количеством листьев: различия между версиями
Перейти к навигации
Перейти к поиску
Остовное дерево с максимальным количеством листьев (посмотреть исходный код)
Версия от 12:58, 12 августа 2016
, 12 августа 2016нет описания правки
Irina (обсуждение | вклад) Нет описания правки |
Irina (обсуждение | вклад) Нет описания правки |
||
| Строка 106: | Строка 106: | ||
Цель (г): алгоритмы аппроксимации с полиномиальным временем выполнения | Цель (г): алгоритмы аппроксимации с полиномиальным временем выполнения | ||
Теория использования экстремальных структур с полиномиальным временем выполнения напрямую приводит к получению алгоритма аппроксимации МЛОД с константным множителем и p-кратным временем выполнения. Вначале выполним редукцию G при помощи правил кернелизации. Эти правила сохраняют параметры аппроксимации. Возьмем любое дерево T (не обязательно остовное) в G. Если выполняются все утверждения касательно структуры, тогда (согласно рассуждениям граничной леммы) дерево T должно иметь не менее n/c листьев для c = 3,75. Таким образом, восстановив T благодаря обращению редукции, получим c- | Теория использования экстремальных структур с полиномиальным временем выполнения напрямую приводит к получению алгоритма аппроксимации МЛОД с константным множителем и p-кратным временем выполнения. Вначале выполним редукцию G при помощи правил кернелизации. Эти правила сохраняют параметры аппроксимации. Возьмем любое дерево T (не обязательно остовное) в G. Если выполняются все утверждения касательно структуры, тогда (согласно рассуждениям граничной леммы) дерево T должно иметь не менее n/c листьев для c = 3,75. Таким образом, восстановив T благодаря обращению редукции, получим c-аппроксимацию. | ||