Введение
В теории графов, связное доминирующее множество и максимальное остовное дерево с листьями – это две тесно связанные структуры, определенные на неориентированном графе.
Алгоритмы
NP-полным является определение, существует ли связное доминирующее множество размером меньше заданного порога, или, эквивалентно, существует ли остовное дерево с не менее чем заданным числом листьев. Поэтому предполагается, что задачу о минимальном связном доминирующем множестве и задачу о максимальном остовном дереве с листьями нельзя решить за полиномиальное время. С точки зрения алгоритмов аппроксимации, связное доминирование и максимальное остовное дерево с листьями не эквивалентны: аппроксимация одного с заданной точностью не то же самое, что аппроксимация другого с той же точностью. Существует аппроксимация для минимального связного доминирующего множества, достигающая коэффициента 2 ln Δ + O(1), где Δ – максимальная степень вершины в графе G. Задача о максимальном остовном дереве с листьями является MAX SNP-трудной, что подразумевает малую вероятность существования полиномиальной схемы аппроксимации. Однако её можно аппроксимировать с точностью до 2 за полиномиальное время. Обе задачи могут быть решены на графах с n вершинами за время O(1.9^n). Задача о максимальном количестве листьев является фиксированно-параметрически разрешимой, то есть её можно решить за время, экспоненциальное по количеству листьев, но полиномиальное по размеру входного графа. Значение кламы этих алгоритмов (интуитивно, количество листьев, до которого задача может быть решена за разумное время) постепенно увеличивалось по мере улучшения алгоритмов для задачи, приблизительно до 37, и было предложено, что можно достичь как минимум 50. В графах максимальной степени три связное доминирующее множество и соответствующая ему задача о максимальном остовном дереве с листьями могут быть решены за полиномиальное время путем сведения их к экземпляру задачи о четности матроида для линейных матроидов.
The maximum leaf spanning tree problem is MAX SNP hard, implying that no polynomial time approximation scheme is likely. However, it can be approximated to within a factor of 2 in polynomial time. Both problems may be solved, on n vertex graphs, in time O(1.9^(n)). The maximum leaf problem is fixed parameter tractable, meaning that it can be solved in time exponential in the number of leaves but only polynomial in the input graph size. The klam value of these algorithms (intuitively, a number of leaves up to which the problem can be solved within a reasonable amount of time) has gradually increased, as algorithms for the problem have improved, to approximately 37, and it has been suggested that at least 50 should be achievable. In graphs of maximum degree three, the connected dominating set and its complementary maximum leaf spanning tree problem can be solved in polynomial time, by transforming them into an instance of the matroid parity problem for linear matroids.
Приложения
Соединенные доминирующие множества полезны для вычисления маршрутов в мобильных ad hoc сетях. В этом применении небольшой соединенный доминирующий набор используется как основа для коммуникаций, а узлы, не входящие в этот набор, общаются, передавая сообщения через соседей, которые в него входят. Максимальное число листьев использовалось при разработке алгоритмов, разрешимых за фиксированное время: несколько NP-трудных задач оптимизации могут быть решены за полиномиальное время для графов с ограниченным максимальным числом листьев.