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

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