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

Отметим, что для гомогенных беспроводных сетей, моделируемых графами единичных дисков, выполняется следующее наблюдение: стоимость построенной магистрали не более чем в <math>min(18 \; log \; (\Delta + 1), 4 \delta + 1) + 10</math> раз превышает оптимальную. Преимущество построенной магистрали заключается в том, что ее полная стоимость мала по сравнению с оптимальной в случае, когда стоимости беспроводных вершин являются сглаженными (т.е. стоимости смежных вершин отличаются на небольшой константный коэффициент), либо в случае, если максимальная степень вершины невелика.

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