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.

  • $\begingroup$ my interest is in both the upper bound as well as the lower bound. $\endgroup$ – user5153 Jul 5 '11 at 19:24
  • $\begingroup$ also i am specifically more interested in algorithms which return tree of optimum cost and violate only the diameter constraint. $\endgroup$ – user5153 Jul 5 '11 at 19:46
  • 1
    $\begingroup$ 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. $\endgroup$ – Mohammad Al-Turkistany Jul 6 '11 at 12:20
  • $\begingroup$ @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. $\endgroup$ – user5153 Jul 6 '11 at 18:54
  • 1
    $\begingroup$ Does this paper have any ideas that might be of use: math.tau.ac.il/~hassin/diameter_95.pdf $\endgroup$ – Joseph Malkevitch Jul 7 '11 at 1:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.