1294
правки
Остовное дерево с максимальным количеством листьев: различия между версиями
Материал из WEGA
Остовное дерево с максимальным количеством листьев (посмотреть исходный код)
Версия от 04:55, 22 ноября 2024
, 22 ноября 2024→Литература
Irina (обсуждение | вклад) мНет описания правки |
KVN (обсуждение | вклад) |
||
| (не показана 1 промежуточная версия 1 участника) | |||
| Строка 43: | Строка 43: | ||
(в) Градиенты и правила преобразования для эвристик локального поиска. | (в) Градиенты и правила преобразования для эвристик локального поиска. | ||
(г) | (г) Аппроксимационные алгоритмы с полиномиальным временем выполнения и границы эффективности, доказанные систематическим образом. | ||
(д) Структура, используемая для решения других задач. | (д) Структура, используемая для решения других задач. | ||
| Строка 107: | Строка 107: | ||
'''Цель (г): алгоритмы | '''Цель (г): аппроксимационные алгоритмы с полиномиальным временем выполнения''' | ||
Теория использования экстремальных структур с полиномиальным временем выполнения напрямую приводит к получению алгоритма | Теория использования экстремальных структур с полиномиальным временем выполнения напрямую приводит к получению аппроксимационного алгоритма ОДМЛ с константным множителем и полиномиальным временем выполнения. Вначале выполним редукцию G при помощи правил кернелизации. Правила редукции сохраняют параметры аппроксимации. Возьмем любое дерево T (не обязательно остовное) в графе G. Если выполняются все утверждения касательно структуры, тогда (согласно рассуждениям граничной леммы) дерево T должно иметь не менее n/c листьев для c = 3,75. Таким образом, восстановив T с учетом произведенной редукции, получим c-аппроксимацию. | ||
| Строка 196: | Строка 196: | ||
17. Solis-Oba, R.: 2-approximation algorithm for finding a spanning tree with the maximum number of leaves. In: Proceedings of the 6th Annual European Symposium on Algorithms (ESA'98). Lecture Notes in Computer Science, vol. 1461, pp. 441-452. Springer, Berlin (1998) | 17. Solis-Oba, R.: 2-approximation algorithm for finding a spanning tree with the maximum number of leaves. In: Proceedings of the 6th Annual European Symposium on Algorithms (ESA'98). Lecture Notes in Computer Science, vol. 1461, pp. 441-452. Springer, Berlin (1998) | ||
[[Категория: Совместное определение связанных терминов]] | |||
