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

Question

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 solve 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.

Answer 1

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.