# Maximize sum of edge weights on spanning tree

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?

## 1 Answer

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

• How do I code degree constrained spanning tree as in instance of this problem? Jan 14 at 16:48
• Hmm, I guess the linked problem is only a relaxation (degree at most $k$ rather than a specified degree sequence). Jan 14 at 17:43
• 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. Jan 14 at 20:50
• But,I am not sure DCST can reduce to this problem Jan 15 at 7:23