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

В общем случае топология беспроводной сенсорной сети представляет собой граф дисков; иначе говоря, каждая вершина ассоциируется с диском. Разные диски могут иметь различный размер. Дуга из вершины u в вершину v существует в том и только том случае, если диск u покрывает v. Виртуальная магистраль в графах дисков представляет собой подмножество вершин, порождающее сильно связный подграф, такой, что каждая вершина, не принадлежащая к подмножеству, имеет входящую дугу из вершины подмножества, а также исходящую дугу, ведущую к вершине подмножества. Такая виртуальная магистраль может рассматриваться как связное доминирующее множество в графе дисков. Вопрос о том, существует ли аппроксимация с полиномиальным временем исполнения и константным коэффициентом эффективности, до сих пор остается открытым. Тай и коллеги [23] достигли в этом отношении определенных успехов.