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

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