4551
правка
Остовное дерево с максимальным количеством листьев: различия между версиями
Перейти к навигации
Перейти к поиску
м
Остовное дерево с максимальным количеством листьев (посмотреть исходный код)
Версия от 22:46, 29 августа 2016
, 29 августа 2016нет описания правки
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) мНет описания правки |
||
| Строка 46: | Строка 46: | ||
(д) Структура, используемая для решения других задач. | (д) Структура, используемая для решения других задач. | ||
== Основные результаты == | == Основные результаты == | ||
| Строка 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]. Должны ли аннотации быть непременным компонентом рецепта наилучшего возможного алгоритма кернелизации с полиномиальным временем выполнения? | ||
== См. также == | == См. также == | ||