约束度+有界直径最小生成树的算法？

Question

假设我有3种限制到计算生成树：

1. 约束程度（例如：在 的节点的生成树可以仅 连接到其他3个节点）
2. 界直径（例如：所有边的' 权重，一旦总和，不能超过 100）。
   2.1。如果可能，请显示符合此标准的所有子树。
3. 两个

有没有什么好的算法来解决这个问题是不是要去开车送我疯了吗？我必须用相当大的插入点（1000多个节点）来运行它，所以它的复杂性也不能太高。

Answer 1

度约束生成树问题是NP完全的。见http://en.wikipedia.org/wiki/Degree-constrained_spanning_tree。 因此，没有好的（即多项式）算法。虽然有近似算法。

谷歌搜索似乎表明，有界直径生成树问题同样困难。