Алгоритм (ы) для ограниченной степени + минимального связующего дерева с ограниченным диаметром?

Question

Предположим, у меня есть 3 вида ограничений на вычисление связующего дерева:

1. Ограниченная степень (например: узел в связующем дереве может быть связан только с 3 другими узлами)
2. Ограниченный диаметр (например: вес всех ребер после суммирования не может превышать 100).
   2.1.Если возможно, покажите все поддеревья, которые соответствуют этому критерию.
3. Оба

Есть ли какие-нибудь хорошие алгоритмы для решения этой проблемы, которые не приведут меня в бешенство?Мне нужно выполнить это с довольно большими входами (более 1000 узлов), поэтому его сложность также не может быть слишком высокой.

Answer 1

Задача связующего дерева со степенью ограничения является NP-полной. См. http://en.wikipedia.org/wiki/Degree-constrained_spanning_tree. Таким образом, нет хороших (то есть, полиномиальных) алгоритмов. Однако существуют алгоритмы аппроксимации.

Похоже, что поиск Google показывает, что проблема связующего дерева с ограниченным диаметром одинаково трудна.