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

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

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

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

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