4551
правка
Взвешенное связное доминирующее множество: различия между версиями
Перейти к навигации
Перейти к поиску
м
Взвешенное связное доминирующее множество (посмотреть исходный код)
Версия от 22:54, 30 июля 2016
, 30 июля 2016→Основные результаты
Irina (обсуждение | вклад) м (→Нотация) |
Irina (обсуждение | вклад) |
||
| Строка 24: | Строка 24: | ||
== Основные результаты == | == Основные результаты == | ||
Поскольку построение взвешенных доминирующих множеств с минимальными весами является NP-полной задачей, исследователи изучали централизованные алгоритмы аппроксимации для этой задачи [3, 7, 9]. В работе [9] Клейн и Рави предложили алгоритм аппроксимации для построения дерева Штейнера с взвешенными вершинами. Обобщение этого алгоритма позволяет получить O(log Л)-аппроксимацию задачи МВСДМ. Гуха и Хуллер [ ] также исследовали алгоритмы аппроксимации для построения дерева Штейнера с взвешенными вершинами и МВСДМ. Для решения последней они разработали алгоритм с коэффициентом аппроксимации (1 | Поскольку построение взвешенных доминирующих множеств с минимальными весами является 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]) вычисляется множество вершин, называемых коннекторами, для соединения этих доминаторов в магистраль. Ван и коллеги доказали, что полная стоимость построенной магистрали не более чем в min( | В работах [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> раз превышает стоимость оптимального решения. | ||
| Строка 50: | Строка 50: | ||
Отметим, что для гомогенных беспроводных сетей, моделируемых графами единичных дисков, выполняется следующее наблюдение: стоимость построенной магистрали не более чем в min(18log(Z\ + 1); 4<5 + 1) + 10 раз превышает оптимальную. Преимущество построенной магистрали заключается в том, что ее полная стоимость мала по сравнению с оптимальной в случае, когда стоимости беспроводных вершин являются сглаженными (т.е. стоимости смежных вершин отличаются на небольшой константный коэффициент), либо в случае, если максимальная степень вершины невелика. | Отметим, что для гомогенных беспроводных сетей, моделируемых графами единичных дисков, выполняется следующее наблюдение: стоимость построенной магистрали не более чем в min(18log(Z\ + 1); 4<5 + 1) + 10 раз превышает оптимальную. Преимущество построенной магистрали заключается в том, что ее полная стоимость мала по сравнению с оптимальной в случае, когда стоимости беспроводных вершин являются сглаженными (т.е. стоимости смежных вершин отличаются на небольшой константный коэффициент), либо в случае, если максимальная степень вершины невелика. | ||
С точки зрения сложности вычисления наиболее продолжительным этапом данного распределенного алгоритма является построение минимального остовного дерева. Кун и др. [10] привели нижнюю границу распределенной временной сложности любого распределенного алгоритма, вычисляющего минимальное доминирующее множество на графе. В сущности, авторы доказали, что даже в случаях без требований связности и взвешенности любой распределенный алгоритм аппроксимации с гарантированным получением полилогарифмической аппроксимации для этой задачи должен иметь сложность не ниже | С точки зрения сложности вычисления наиболее продолжительным этапом данного распределенного алгоритма является построение минимального остовного дерева. Кун и др. [10] привели нижнюю границу распределенной временной сложности любого распределенного алгоритма, вычисляющего минимальное доминирующее множество на графе. В сущности, авторы доказали, что даже в случаях без требований связности и взвешенности любой распределенный алгоритм аппроксимации с гарантированным получением полилогарифмической аппроксимации для этой задачи должен иметь сложность не ниже | ||
== Применение == | == Применение == | ||