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

Question

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

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

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

Answer 1

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

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