Algorithm(s) for the constrained degree + bounded diameter minimum spanning tree?

Suppose I have 3 kinds of restrictions to computing a spanning tree:

1. Constrained degree (eg: a node in a spanning tree may only be connected up to 3 other nodes)
2. Bounded diameter (eg: all edges' weights, once summed, cannot exceed 100).

   2.1. If possible, show all subtrees that meet this criteria.

3. Both

Are there any good algorithms to 开发者_如何学Csolve this that aren't gonna drive me insane? I'm gonna have to run this with rather large inpputs (1000+ nodes), so its complexity can't be too high either.

The degree-constrained spanning tree problem is NP-complete. See http://en.wikipedia.org/wiki/Degree-constrained_spanning_tree . So, no good (i.e., polynomial) algorithms. There are approximation algorithms, though.

A Google search seems to indicate that the bounded diameter spanning tree problem is equally hard.