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

Question

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

1. 约束度（例如： 生成树可能只 连接最多 3 个其他节点）
2. 有界直径（例如：所有边' 权重一旦相加，就不能超过 100).
   2.1.如果可能，显示满足此条件的所有子树。
3. 有没有

什么好的算法可以解决这个问题，而且不会让我发疯？我将不得不使用相当大的输入（1000+ 个节点）来运行它，因此它的复杂性也不能太高。

Answer 1

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

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