Охватывающее дерево с ограниченной степенью

В теории графов остовное дерево с ограничением степени — это остовное дерево , в котором максимальная степень вершины ограничена некоторой константой k . Задача остовного дерева с ограничением степени заключается в определении того, имеет ли конкретный граф такое остовное дерево для конкретного k .

Вход: неориентированный граф G(V,E) с n узлами; положительное целое число k < n .

Вопрос: Имеет ли G остовное дерево, в котором ни один узел не имеет степени больше k ?

Эта задача является NP-полной (Garey & Johnson 1979). Это можно показать с помощью сведения к задаче о гамильтоновом пути . Она остается NP-полной, даже если k зафиксировано на значении ≥ 2. Если задача определена как степень, которая должна быть ≤  k , случай k = 2 остовного дерева с ограниченной степенью является задачей о гамильтоновом пути.

На взвешенном графе минимальное остовное дерево с ограничением степени (DCMST) — это остовное дерево с ограничением степени, в котором сумма его ребер имеет минимально возможную сумму. Нахождение DCMST — это NP-трудная задача. ^[1]

Были предложены эвристические алгоритмы, которые могут решить эту задачу за полиномиальное время, включая генетические и муравьиные алгоритмы.

Фюрер и Рагхавачари (1994) предлагают итеративный полиномиальный алгоритм времени, который, учитывая граф , возвращает остовное дерево с максимальной степенью не больше , где — минимально возможная максимальная степень среди всех остовных деревьев. Таким образом, если , такой алгоритм вернет либо остовное дерево максимальной степени , либо .${\displaystyle G}$${\displaystyle \Дельта ^{*}+1}$${\displaystyle \Дельта ^{*}}$${\displaystyle k=\Дельта ^{*}}$${\displaystyle к}$${\displaystyle к+1}$

• Гэри, Майкл Р.; Джонсон , Дэвид С. (1979), Компьютеры и неразрешимость: Руководство по теории NP-полноты , WH Freeman, ISBN 978-0-7167-1045-5. A2.1: ND1, стр. 206.{{citation}}: CS1 maint: постскриптум ( ссылка )
• Фюрер, Мартин; Рагхавачари, Баладжи (1994), «Аппроксимация дерева Штейнера минимальной степени с точностью до оптимальной», Журнал алгоритмов , 17 (3): 409–423, CiteSeerX  10.1.1.136.1089 , doi :10.1006/jagm.1994.1042.