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

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