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

Теорема 1. Для сети, моделируемой графом G, алгоритм 1 из работы [12, 13] строит доминирующее множество, полная стоимость которого не более чем в <math>min( \alpha^{ [2] } (G) \; log \; (\Delta + 1), (\alpha^{ [1] } (G) - 1) \delta + 1) </math> раз превышает оптимальную.

Теорема 3. Для любого коммуникационного графа G алгоритмы 1 и 2 строят взвешенное связное доминирующее множество, полная стоимость которого не более чем в <math>min( \alpha^{ [2] } (G) \; log \; (\Delta + 1), (\alpha^{ [1] } (G) - 1) \delta + 1) + 2\alpha^{ [1] } (G)</math> раз превышает оптимальную.