4430
правок
Остовное дерево с максимальным количеством листьев: различия между версиями
Материал из WEGA
Остовное дерево с максимальным количеством листьев (посмотреть исходный код)
Версия от 13:58, 1 октября 2023
, 1 октября 2023нет описания правки
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) мНет описания правки |
||
| (не показана 1 промежуточная версия этого же участника) | |||
| Строка 43: | Строка 43: | ||
(в) Градиенты и правила преобразования для эвристик локального поиска. | (в) Градиенты и правила преобразования для эвристик локального поиска. | ||
(г) | (г) Аппроксимационные алгоритмы с полиномиальным временем выполнения и границы эффективности, доказанные систематическим образом. | ||
(д) Структура, используемая для решения других задач. | (д) Структура, используемая для решения других задач. | ||
== Основные результаты == | == Основные результаты == | ||
| Строка 106: | Строка 107: | ||
'''Цель (г): алгоритмы | '''Цель (г): аппроксимационные алгоритмы с полиномиальным временем выполнения''' | ||
Теория использования экстремальных структур с полиномиальным временем выполнения напрямую приводит к получению алгоритма | Теория использования экстремальных структур с полиномиальным временем выполнения напрямую приводит к получению аппроксимационного алгоритма ОДМЛ с константным множителем и полиномиальным временем выполнения. Вначале выполним редукцию G при помощи правил кернелизации. Правила редукции сохраняют параметры аппроксимации. Возьмем любое дерево T (не обязательно остовное) в графе G. Если выполняются все утверждения касательно структуры, тогда (согласно рассуждениям граничной леммы) дерево T должно иметь не менее n/c листьев для c = 3,75. Таким образом, восстановив T с учетом произведенной редукции, получим c-аппроксимацию. | ||
| Строка 133: | Строка 134: | ||
== Применение == | == Применение == | ||
Задача построения остовного дерева с максимальным количеством листьев применяется в расчетах компьютерной графики с целью создания представлений полосы треугольников для быстрого интерактивного рендеринга [5]. Также она находит применение в области перераспределения трафика и проектирования сетей – например, для проектирования оптических сетей и распределения используемых длин волн для снижения стоимости сети – в терминах оконечного оборудования либо электронных переключателей [6]. Задача о минимальной энергии в беспроводных сетях заключается в нахождении радиус-вектора передачи для всех станций таким образом, чтобы полная мощность излучения всей сети была насколько возможно малой. Ограниченная версия этой задачи эквивалентна задаче нахождения остовного дерева с максимальным количеством листьев [7]. Задача поиска остовных деревьев с большим числом листьев эквивалентна задаче поиска небольших связных доминирующих множеств и в связи с этим также носит название задачи о минимальном связном доминирующем множестве [13]. | Задача построения остовного дерева с максимальным количеством листьев применяется в расчетах компьютерной графики с целью создания представлений полосы треугольников для быстрого интерактивного рендеринга [5]. Также она находит применение в области перераспределения трафика и проектирования сетей – например, для проектирования оптических сетей и распределения используемых длин волн для снижения стоимости сети – в терминах оконечного оборудования либо электронных переключателей [6]. Задача о минимальной энергии в беспроводных сетях заключается в нахождении радиус-вектора передачи для всех станций таким образом, чтобы полная мощность излучения всей сети была насколько возможно малой. Ограниченная версия этой задачи эквивалентна задаче нахождения остовного дерева с максимальным количеством листьев [7]. Задача поиска остовных деревьев с большим числом листьев эквивалентна задаче поиска небольших связных доминирующих множеств и в связи с этим также носит название задачи о минимальном связном доминирующем множестве [13]. | ||
== Открытые вопросы == | == Открытые вопросы == | ||
| Строка 153: | Строка 155: | ||
Можно рассмотреть обобщенную задачу построения остовного дерева с максимальным количеством листьев (MAX LEAF), в которой вершины и ребра имеют различные аннотации, говорящие о том, какие вершины ''должны'' быть листьями (или внутренними вершинами) в решении, и т.д. В общем случае подобная обобщенная форма задачи будет сложнее вышеописанной более простой формы. Однако некоторые из «наиболее известных» FPT-алгоритмов для решения различных задач основаны на таких обобщенных формах с аннотациями. В качестве примеров можно привести алгоритмы нахождения доминирующего множества для планарного графа (PLANAR DOMINATING SET) и разрывающего множества вершин (FEEDBACK VERTEX SET) [4]. Должны ли аннотации быть непременным компонентом рецепта наилучшего возможного алгоритма кернелизации с полиномиальным временем выполнения? | Можно рассмотреть обобщенную задачу построения остовного дерева с максимальным количеством листьев (MAX LEAF), в которой вершины и ребра имеют различные аннотации, говорящие о том, какие вершины ''должны'' быть листьями (или внутренними вершинами) в решении, и т.д. В общем случае подобная обобщенная форма задачи будет сложнее вышеописанной более простой формы. Однако некоторые из «наиболее известных» FPT-алгоритмов для решения различных задач основаны на таких обобщенных формах с аннотациями. В качестве примеров можно привести алгоритмы нахождения доминирующего множества для планарного графа (PLANAR DOMINATING SET) и разрывающего множества вершин (FEEDBACK VERTEX SET) [4]. Должны ли аннотации быть непременным компонентом рецепта наилучшего возможного алгоритма кернелизации с полиномиальным временем выполнения? | ||
== См. также == | == См. также == | ||
