Локальные вычисления в неструктурированных радиосетях: различия между версиями

'''Определение 2 ([[минимальное доминирующее множество]])'''. Пусть дан граф G = (V, E). Доминирующее множество представляет собой подмножество <math>S \subseteq V</math>, такое, что каждая вершина графа либо находится в S, либо имеет хотя бы одного соседа в S. В задаче о минимальном доминирующем множестве требуется найти доминирующее множество S минимальной мощности.

Доминирующее множество <math>S \subseteq V/math>, в котором никакие две соседних вершины не входят в S, является ''максимальным независимым множеством''. Распределенная сложность вычисления максимального независимого множества в модели передачи сообщений представляет фундаментальный интерес для сообщества распределенных вычислений уже более двух десятилетий (см, например, [11, 12, 13]), но о сложности этой задачи в моделях радиосетей известно гораздо меньше.

'''Определение 3 (максимальное независимое множество)'''. Пусть дан граф G = (V, E). Независимое множество представляет собой подмножество попарно не смежных вершин в графе G. Максимально независимое множество в G – это независимое множество <math>S \subseteq V/math>, такое, что для каждой вершины <math>u \notin S</math> существует вершина <math>v in (u)</math> в S.