Опорное дерево с ограничением по степени

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

Формальное определение

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

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

NP-полнота

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

Минимальное остовное дерево с ограничением по степени

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

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

Алгоритм аппроксимации

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

Ссылки

^ Буи, Т.Н. и Зрнчич, К.М. 2006. Алгоритм на основе муравьев для поиска минимального остовного дерева с ограничением по степени. В GECCO '06: Материалы 8-й ежегодной конференции по генетическим и эволюционным вычислениям, страницы 11–18, Нью-Йорк, штат Нью-Йорк, США. АКМ.

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

[1] Буи, Т.Н. и Зрнчич, К.М. 2006. Алгоритм на основе муравьев для поиска минимального остовного дерева с ограничением по степени. В GECCO '06: Материалы 8-й ежегодной конференции по генетическим и эволюционным вычислениям, страницы 11–18, Нью-Йорк, штат Нью-Йорк, США. АКМ.

[1]