0
$\begingroup$

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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

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

Improve this answer
$\endgroup$
4
  • $\begingroup$ How do I code degree constrained spanning tree as in instance of this problem? $\endgroup$
    – Ben Barber
    Jan 14, 2021 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, 2021 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, 2021 at 20:50
  • $\begingroup$ But,I am not sure DCST can reduce to this problem $\endgroup$
    – Max David
    Jan 15, 2021 at 7:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.