We consider the problem of finding a minimum diameter spanning tree with maximum node degree B in a complete undirected edge-weighted graph. We prove that the problem is NP-complete, and provide an O((log_B n)~(1/2))-approximation algorithm for the problem. Our algorithm is purely combinatorial, and relies on a combination of filtering and divide and conquer.
展开▼
