# Results regarding Bounded Diameter Minimum Spanning Tree

Given edge weighted undirected graph the problem asks to output a spanning tree $T$ of minimum weight such that the path between any two vertices in the tree $T$ is bounded by the input $k$. One of the related paper is at http://www.sciencedirect.com/science/article/pii/S0166218X99001110 .

However i could not find other relevant results which improvised over it in general case. Can anyone please refer me the state of the art in this problem. I am also looking for results on unweighted undirected graphs which i couldn't get. I tried to google out and follow the citations but couldn't get what i wanted.

• my interest is in both the upper bound as well as the lower bound. – user5153 Jul 5 '11 at 19:24
• also i am specifically more interested in algorithms which return tree of optimum cost and violate only the diameter constraint. – user5153 Jul 5 '11 at 19:46
• The problem is NP-complete if the diameter bound is greater than 3 and even if edge weights are restricted to {1, 2}. It is solvable in polynomial time when all edge weights are identical or when the bound is less than or equal 3. – Mohammad Al-Turkistany Jul 6 '11 at 12:20
• @Mohammad Al-Turkistany yes i realized the problem on graphs having equal weight is in P. Thanks for that. However im looking for more results as described above in question and comments. – user5153 Jul 6 '11 at 18:54
• Does this paper have any ideas that might be of use: math.tau.ac.il/~hassin/diameter_95.pdf – Joseph Malkevitch Jul 7 '11 at 1:17