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

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

Подмножество S множества V называется [[доминирующее множество|доминирующим множеством]], если каждая вершина V либо принадлежит к S, либо смежна с некоторой вершиной, принадлежащей к S. Вершины S называются доминаторами, а вершины, не входящие в S – доминируемыми вершинами. Подмножество B множества V называется [[связное доминирующее множество|связным доминирующим множеством]] (СДМ), если оно является доминирующим множеством и порождает связный подграф. Следовательно, вершины подмножества В могут «общаться» друг с другом без использования вершин V - B. Доминирующее множество минимальной мощности называется [[минимальное доминирующее множество|минимальным доминирующим множеством]] (МДМ). Связное доминирующее множество минимальной мощности называется [[минимальное связное доминирующее множество|минимальным связным доминирующим множеством]] (МСДМ). Во взвешенной версии каждой вершине u сопоставлена стоимость c(u). В этом случае связное доминирующее множество B называется [[связное взвешенное доминирующее множество|взвешенным связным доминирующим множеством]] (ВСДМ). Подмножество B множества V называется [[минимальное взвешенное связное доминирующее множество|минимальным взвешенным связным доминирующим множеством]] (МВСДМ), если оно является ВСДМ с минимальной полной стоимостью. Хорошо известно, что нахождение множества МСДМ или МВДСМ оказывается NP-полной задачей, даже если G является графом единичных кругов. В работе Вана и др. рассматривались эффективные алгоритмы аппроксимации, вычисляющие магистраль с низкой стоимостью и способные успешно аппроксимировать нахождение МВСДМ. Для заданного коммуникационного графа G = (V, E, C), где V – множество вершин, E – множество ребер, а C – множество весов ребер, соответствующая задача вычисления минимального взвешенного связного доминирующего множества формулируется следующим образом.

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

С точки зрения временной сложности вычисления наиболее продолжительным этапом данного распределенного алгоритма является построение минимального остовного дерева. Кун и др. [10] привели нижнюю границу распределенной временной сложности любого распределенного алгоритма, вычисляющего минимальное доминирующее множество на графе. В сущности, авторы доказали, что даже в случаях без требований связности и взвешенности любой распределенный алгоритм аппроксимации с гарантированным получением полилогарифмической аппроксимации для этой задачи должен иметь временную сложность не ниже <math>\Omega (log \; \Delta / log \; log \; \Delta)</math>.