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

Поскольку построение взвешенных доминирующих множеств с минимальными весами является NP-полной задачей, исследователи изучали централизованные алгоритмы аппроксимации для этой задачи [3, 7, 9]. В работе [9] Клейн и Рави предложили алгоритм аппроксимации для построения дерева Штейнера с взвешенными вершинами. Обобщение этого алгоритма позволяет получить O(log Л)-аппроксимацию задачи МВСДМ. Гуха и Хуллер [7] также исследовали алгоритмы аппроксимации для построения дерева Штейнера с взвешенными вершинами и МВСДМ. Для решения последней они разработали алгоритм с коэффициентом аппроксимации <math>(1,35 + \epsilon) \; log \; \Delta</math> для любого фиксированного значения <math>\epsilon > 0 \;</math>. Недавно Амбул и др. [3] предложили константный алгоритм аппроксимации задачи МВСДМ для модели графов единичных дисков. Коэффициент аппроксимации их алгоритма ограничен 89. Все эти алгоритмы являются централизованными, в то же время в приложениях для децентрализованных беспроводных сетей обычно используются распределенные алгоритмы построения МВСДМ.

В работах [12, 13] Ван и коллеги предложили распределенный алгоритм построения взвешенного связного доминирующего множества для децентрализованной беспроводной сети G, состоящий из двух этапов: на первом этапе (этап кластеризации, алгоритм 1 в [12, 13]) вычисляется множество беспроводных вершин, являющихся доминаторами (центральных узлов); на втором этапе (алгоритм 2 в [12,13]) вычисляется множество вершин, называемых коннекторами, для соединения этих доминаторов в магистраль. Ван и коллеги доказали, что полная стоимость построенной магистрали не более чем в <math>min( \alpha^{ [2] } (G) \; log \; (\Delta + 1), (\alpha^{ [1] } (G) - 1) \delta + 1) + 2\alpha^{ [1] } (G)</math> раз превышает стоимость оптимального решения.

Вначале алгоритм 1 строит максимальное независимое множество, используя классический жадный метод, в котором критерием выбора служит стоимость вершины. Затем для каждой вершины v, принадлежащей к максимальному независимому множеству, алгоритм запускает локальный жадный метод поиска покрытия множества на [[локальная окрестность|локальной окрестности]] <math>N_2(v) \;</math>, который находит некоторые вершины <math>(GRDY_v) \;</math>, покрывающие всех соседей v, доступных в результате одного перехода. Если общая стоимость <math>(GRDY_v) \;</math> меньше, чем у v, то алгоритм использует <math>(GRDY_v) \;</math> вместо v, что снижает стоимость максимального независимого множества. Следующая теорема о значении полной стоимости выбранного таким образом множества была доказана в [12, 13].