Взвешенное связное доминирующее множество: различия между версиями
Irina (обсуждение | вклад) (Новая страница: «== Ключевые слова и синонимы == Минимальное взвешенное связное доминирующее множество == …») |
Irina (обсуждение | вклад) |
||
| Строка 4: | Строка 4: | ||
== Постановка задачи == | == Постановка задачи == | ||
Задача представляет собой вариант классической задачи вычисления минимального связного доминирующего множества с учетом весов. Она имеет множество вариантов практического применения, в частности, в области беспроводных сетей и распределенных систем. В предыдущих работах [1, 2, 4, 5, 6, 14] по беспроводным сетям основное внимание уделялось разработке эффективных распределенных алгоритмов для построения связного доминирующего множества, которое можно было бы использовать в качестве виртуальной магистрали сети. | Задача представляет собой вариант классической задачи вычисления минимального связного доминирующего множества с учетом весов. Она имеет множество вариантов практического применения, в частности, в области беспроводных сетей и распределенных систем. В предыдущих работах [1, 2, 4, 5, 6, 14] по беспроводным сетям основное внимание уделялось разработке эффективных распределенных алгоритмов для построения связного доминирующего множества, которое можно было бы использовать в качестве виртуальной магистрали сети. Большинство предложенных методов стремятся минимизировать количество вершин в магистрали (т.е. число центральных узлов). Однако для многих приложений минимизации размера магистрали будет недостаточно. Например, в беспроводных сетях различные вершины могут иметь различную стоимость обслуживания в качестве центрального узла из-за различий в типах устройств, энергоемкости и объеме информации, подлежащей обработке. | ||
Версия от 14:24, 28 июля 2016
Ключевые слова и синонимы
Минимальное взвешенное связное доминирующее множество
Постановка задачи
Задача представляет собой вариант классической задачи вычисления минимального связного доминирующего множества с учетом весов. Она имеет множество вариантов практического применения, в частности, в области беспроводных сетей и распределенных систем. В предыдущих работах [1, 2, 4, 5, 6, 14] по беспроводным сетям основное внимание уделялось разработке эффективных распределенных алгоритмов для построения связного доминирующего множества, которое можно было бы использовать в качестве виртуальной магистрали сети. Большинство предложенных методов стремятся минимизировать количество вершин в магистрали (т.е. число центральных узлов). Однако для многих приложений минимизации размера магистрали будет недостаточно. Например, в беспроводных сетях различные вершины могут иметь различную стоимость обслуживания в качестве центрального узла из-за различий в типах устройств, энергоемкости и объеме информации, подлежащей обработке.