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

Коммуникационный граф G = (V, E) над множеством беспроводных вершин V содержит ребро uv между вершинами u и v в том и только том случае, если u и v могут напрямую связываться друг с другом, т.е. находятся в пределах областей передачи друг друга. Пусть dG(u) – степень вершины u в графе G, а Л – максимальная степень среди всех беспроводных вершин (т.е. Л = maxu2V dG(u)). Каждой вершине u сопоставлена стоимость c(u) принадлежности к магистрали. Пусть 8 = maxij2E c(i)/c(j), где ij – ребро между вершинами i и j, E – множество коммуникационных каналов в беспроводной сети G, а операция взятия максимума производится над всеми парами смежных вершин i и j в G. Иными словами, S представляет собой максимальное отношение стоимостей двух смежных вершин и может быть названо гладкостью стоимостей сети. Если S ограничено некоторой небольшой константой, стоимости вершин являются гладкими. Если область передачи каждой беспроводной вершины моделируется единичным диском с этой вершиной в центре, то коммуникационный граф называют графом единичных дисков и обозначают как UDG(V). Такие сети также называются гомогенными сетями.

Подмножество S множества V называется доминирующим множеством, если каждая вершина V либо принадлежит к S, либо смежна с некоторой вершиной, принадлежащей к S. Вершины S называются доминаторами, а вершины, не входящие в S – доминируемыми вершинами. Подмножество B множества V называется связным доминирующим множеством (СДМ), если оно является доминирующим множеством и порождает связный подграф. Следовательно, вершины подмножества В могут «общаться» друг с другом без использования вершин V — B. Доминирующее множество минимальной мощности называется минимальным доминирующим множеством (МДМ). Связное доминирующее множество минимальной мощности называется минимальным связным доминирующим множеством (МСДМ). Во взвешенной версии каждой вершине u сопоставлена стоимость c(u). В этом случае связное доминирующее множество B называется взвешенным связным доминирующим множеством (ВСДМ). Подмножество B множества V называется минимальным взвешенным связным доминирующим множеством (МВСДМ), если оно является ВСДМ с минимальной полной стоимостью. Хорошо известно, что нахождение множеств МСДМ и МВДСМ оказывается NP-полной задачей, даже если G является графом единичных дисков. В работе Вана и др. рассматривались эффективные алгоритмы аппроксимации, вычисляющие магистраль с низкой стоимостью и способные успешно аппроксимировать нахождение МВСДМ. Для заданного коммуникационного графа G = (V, E, C), где V – множество вершин, E – множество ребер, а C – множество весов ребер, соответствующая задача вычисления минимального взвешенного связного доминирующего множества формулируется следующим образом.