Approximating the degree-bounded minimum diameter spanning tree problem
2003
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)-approximation algorithm for the problem. Our algorithm is purely combinatorial, and relies on a combination of filtering and divide and conquer.
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
25
References
5
Citations
NaN
KQI