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

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

Коммуникационный граф G = (V, E) над множеством беспроводных вершин V содержит ребро uv между вершинами u и v в том и только том случае, если u и v могут напрямую связываться друг с другом, т.е. находятся в пределах областей передачи друг друга. Пусть <math>d_G(u) \;</math> – степень вершины u в графе G, а <math>\Delta \;</math> – максимальная степень среди всех беспроводных вершин (т.е. <math>\Delta = max_{u \in V} \; d_G(u) \;</math>). Каждой беспроводной вершине u сопоставлена стоимость принадлежности к магистрали – c(u). Пусть <math>\delta = max_{ij \in E} \; c(i)/c(j) \;</math>, где ij – ребро между вершинами i и j, E – множество коммуникационных каналов в беспроводной сети G, а операция взятия максимума производится над всеми парами смежных вершин i и j в G. Иными словами, <math>\delta \;</math> представляет собой максимальное отношение стоимостей двух смежных вершин и может быть названо ''сглаженностью стоимостей'' сети. Если <math>\delta \;</math> ограничено некоторой небольшой константой, стоимости вершин являются ''сглаженными''. Если область передачи каждой беспроводной вершины моделируется единичным диском с этой вершиной в центре, то коммуникационный граф называют [[граф единичных дисков|графом единичных дисков]] и обозначают как UDG(V). Такие сети также называются гомогенными сетями.

Подмножество 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 – множество весов ребер, соответствующая задача вычисления минимального взвешенного связного доминирующего множества формулируется следующим образом.

Еще одна родственная задача – вычисление независимого множества. Подмножество вершин графа G является [[независимое множество вершин|независимым множеством]], если никакие две вершины подмножества не соединены ребром. Независимое множество является ''наибольшим'', если к нему нельзя добавить ни одной вершины так, чтобы получилось независимое множество большего размера. Очевидно, что любое наибольшее независимое множество является доминирующим множеством. Независимое множество является [[максимальное независимое множество|максимальным]], если не существует независимого множества с большим количеством вершин. [[Число независимости]] графа G, обозначаемое как <math>\alpha (G) \;</math>, представляет собой размер максимального независимого множества этого графа. ''k-локальное число независимости'', <math>\alpha^{ [k] } (G) \;</math>, определяется как <math>\alpha^{ [k] } (G) = max_{u \in V} \; \alpha (G_k(u)) \;</math>. Здесь <math>G_k(u) \;</math> – граф, порожденный на вершинах G, находящихся от вершины u на расстоянии не более k переходов (обозначается <math>N_k(u) \;</math>), т.е. <math>G_k(u) \;</math> определяется на <math>N_k(u) \;</math> и содержит все ребра G, обе конечных точки которых содержатся в <math>N_k(u) \;</math>. Хорошо известно, что для графа единичных дисков <math>\alpha^{ [1] } (UDG) \le 5 \;</math> [2] и <math>\alpha^{ [2] } (UDG) \le 18 \;</math> [11].

 

Поскольку построение минимальных взвешенных доминирующих множеств является 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>.