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

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

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