Остовное дерево с ограничениями по степени - Degree-constrained spanning tree

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

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

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

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

NP-полнота

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

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

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

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

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

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

Рекомендации

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

Гарей, Майкл Р.; Джонсон, Дэвид С. (1979), Компьютеры и непреодолимость: руководство по теории NP-полноты, W.H. Фриман, ISBN 978-0-7167-1045-5. A2.1: ND1, стр. 206.
Фюрер, Мартин; Рагхавачари, Баладжи (1994), "Приближение дерева Штейнера минимальной степени к одному из оптимальных", Журнал алгоритмов, 17 (3): 409–423, CiteSeerX 10.1.1.136.1089, Дои:10.1006 / jagm.1994.1042.

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

[1]