# 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?

• 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