You are given an undirected and unweighted connected graph $G(V, E)$ for which you've been asked to find a spanning tree that has minimum diameter.

I have an idea but I'm not sure if it's a correct one. Can you give me a feedback?

The algorithm:

let T be an empty forest of trees for v in V color v white for v in (max-to-min-sort V by degree) color v gray for u in adj(v) if u is white add (v, u) to T mark u gray mark v black

The algorithm works on the same principal as Kruskal's algorithm for a MST.

Thank you for your time

  • 1
    $\begingroup$ From what I can see, it does yield a tree (provided $G$ is connected). I would try applying the algorithm to regular graphs and see if it does what you want. I'm skeptical that it gives a min-diameter tree... and I suspect a counter-example can be found among regular graphs. (I haven't been able to find one yet myself though.) $\endgroup$ – TravisJ May 8 '15 at 11:28
  • $\begingroup$ The reason I think a regular-graphs are where to look is because your algorithm tries to make use of high (relative) degree vertices. But, if the graph is regular, then I can add vertices (the v ones that become black first) in any order I want... and I can add their neighbors in any order I want. $\endgroup$ – TravisJ May 8 '15 at 11:32
  • 1
    $\begingroup$ Do not waste your time - the algorithm is extremely buggy. You can see how much using the "Petersen graph". And it does not even builds a tree : / $\endgroup$ – user931392 May 8 '15 at 12:19

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.