約束度+有界直徑最小生成樹的算法？

Question

假設我有3種限制到計算生成樹：

1. 約束程度（例如：在 的節點的生成樹可以僅 連接到其他3個節點）
2. 界直徑（例如：所有邊的' 權重，一旦總和，不能超過 100）。
   2.1。如果可能，請顯示符合此標準的所有子樹。
3. 兩個

有沒有什麼好的算法來解決這個問題是不是要去開車送我瘋了嗎？我必須用相當大的插入點（1000多個節點）來運行它，所以它的複雜性也不能太高。

Answer 1

度約束生成樹問題是NP完全的。見http://en.wikipedia.org/wiki/Degree-constrained_spanning_tree。 因此，沒有好的（即多項式）算法。雖然有近似算法。

谷歌搜索似乎表明，有界直徑生成樹問題同樣困難。