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

Подмножество 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 – множество весов ребер, соответствующая задача вычисления минимального взвешенного связного доминирующего множества формулируется следующим образом.