Problem: Given a complete graph with n vertices, the edge weight between vertex $i$ and vertex $j$ is $b[i]\times b[j]$.

Under the condition that the degree of point $i$ on spanning tree is DEG $[i]$, let the sum of all edge weights on spanning tree is maximized.

I wonder if there is a polynomial time algorithm for this problem.

If so, what should the algorithm do? Why is it right? Has there been any discussion in the academic circle?


This is the degree-constrained spanning tree problem, and it is NP-hard: https://en.wikipedia.org/wiki/Degree-constrained_spanning_tree

  • $\begingroup$ How do I code degree constrained spanning tree as in instance of this problem? $\endgroup$
    – Ben Barber
    Jan 14 at 16:48
  • 1
    $\begingroup$ Hmm, I guess the linked problem is only a relaxation (degree at most $k$ rather than a specified degree sequence). $\endgroup$
    – RobPratt
    Jan 14 at 17:43
  • $\begingroup$ I'm glad I asked for clarification as I hadn't realised that DEG was degree in the spanning tree, although I'm not sure what else would have made sense. $\endgroup$
    – Ben Barber
    Jan 14 at 20:50
  • $\begingroup$ But,I am not sure DCST can reduce to this problem $\endgroup$
    – Max David
    Jan 15 at 7:23

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.