Взвешенное связное доминирующее множество: различия между версиями

Материал из WEGA
Перейти к навигации Перейти к поиску
(Новая страница: «== Ключевые слова и синонимы == Минимальное взвешенное связное доминирующее множество == …»)
 
Строка 4: Строка 4:


== Постановка задачи ==
== Постановка задачи ==
Задача представляет собой вариант классической задачи вычисления минимального связного доминирующего множества с учетом весов. Она имеет множество вариантов практического применения, в частности, в области беспроводных сетей и распределенных систем. В предыдущих работах [1, 2, 4, 5, 6, 14] по беспроводным сетям основное внимание уделялось разработке эффективных распределенных алгоритмов для построения связного доминирующего множества, которое можно было бы использовать в качестве виртуальной магистрали сети.
Задача представляет собой вариант классической задачи вычисления минимального связного доминирующего множества с учетом весов. Она имеет множество вариантов практического применения, в частности, в области беспроводных сетей и распределенных систем. В предыдущих работах [1, 2, 4, 5, 6, 14] по беспроводным сетям основное внимание уделялось разработке эффективных распределенных алгоритмов для построения связного доминирующего множества, которое можно было бы использовать в качестве виртуальной магистрали сети. Большинство предложенных методов стремятся минимизировать количество вершин в магистрали (т.е. число центральных узлов). Однако для многих приложений минимизации размера магистрали будет недостаточно. Например, в беспроводных сетях различные вершины могут иметь различную стоимость обслуживания в качестве центрального узла из-за различий в типах устройств, энергоемкости и объеме информации, подлежащей обработке.

Версия от 14:24, 28 июля 2016

Ключевые слова и синонимы

Минимальное взвешенное связное доминирующее множество


Постановка задачи

Задача представляет собой вариант классической задачи вычисления минимального связного доминирующего множества с учетом весов. Она имеет множество вариантов практического применения, в частности, в области беспроводных сетей и распределенных систем. В предыдущих работах [1, 2, 4, 5, 6, 14] по беспроводным сетям основное внимание уделялось разработке эффективных распределенных алгоритмов для построения связного доминирующего множества, которое можно было бы использовать в качестве виртуальной магистрали сети. Большинство предложенных методов стремятся минимизировать количество вершин в магистрали (т.е. число центральных узлов). Однако для многих приложений минимизации размера магистрали будет недостаточно. Например, в беспроводных сетях различные вершины могут иметь различную стоимость обслуживания в качестве центрального узла из-за различий в типах устройств, энергоемкости и объеме информации, подлежащей обработке.