4551
правка
Взвешенное связное доминирующее множество: различия между версиями
Материал из WEGA
Взвешенное связное доминирующее множество (посмотреть исходный код)
Версия от 22:55, 30 июля 2016
, 30 июля 2016→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 33: | Строка 33: | ||
Теорема 1. Для сети, моделируемой графом G, алгоритм 1 из работы [12, 13] строит доминирующее множество, полная стоимость которого не более чем в | Теорема 1. Для сети, моделируемой графом G, алгоритм 1 из работы [12, 13] строит доминирующее множество, полная стоимость которого не более чем в <math>min( \alpha^{ [2] } (G) \; log \; (\Delta + 1), (\alpha^{ [1] } (G) - 1) \delta + 1) </math> раз превышает оптимальную. | ||
| Строка 45: | Строка 45: | ||
Теорема 3. Для любого коммуникационного графа G алгоритмы 1 и 2 строят взвешенное связное доминирующее множество, полная стоимость которого не более чем в | Теорема 3. Для любого коммуникационного графа G алгоритмы 1 и 2 строят взвешенное связное доминирующее множество, полная стоимость которого не более чем в <math>min( \alpha^{ [2] } (G) \; log \; (\Delta + 1), (\alpha^{ [1] } (G) - 1) \delta + 1) + 2\alpha^{ [1] } (G)</math> раз превышает оптимальную. | ||
