8
$\begingroup$

I have a graph and I need to find a minimum spanning tree to a given graph. What is to be done so that the output obtained is a binary tree?

$\endgroup$
  • $\begingroup$ I just need to know if it is possible or not. I have done some digging though. I just want to know if there is any way to generate a spanning tree which is binary as well. $\endgroup$ – Aditya.M Oct 20 '14 at 7:08
18
$\begingroup$

There is nothing to be done: for instance, let $S_k$ denote the star graph with $k$ leaves. The graph $S_k$ has a unique spanning tree (which is $S_k$ itself), and it has a vertex with degree exactly $k$.

In fact, the general problem of finding a degree-constrained minimum spanning tree is NP-complete.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.