受限度数和有界直径最小生成树的算法？

Question

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

1. 受限度数（例如：生成树中的一个节点只能连接到其他3个节点）
2. 有界直径（例如：所有边的权重总和不能超过100）。
   2.1 如果可能，请显示符合此条件的所有子树。
3. 两者都有

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

- iceburn

Answer 1

度约束生成树问题是NP完全问题。详见http://en.wikipedia.org/wiki/Degree-constrained_spanning_tree。 因此，没有好的（即多项式）算法。不过有近似算法。 谷歌搜索似乎表明有界直径生成树问题同样困难。

- lhf

---

我理解这一点，但我并不寻求最优解。然而，这并不意味着我可以随便自己动手。 - iceburn

他指出的参考文献链接到一篇关于近似算法的论文。 - kunigami