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

Question

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

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

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

Answer 1

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

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