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

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

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

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

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