# Broadcasting in node-weighted graphs

Given an undirected graph $G=(V,E)$ with non-negative node-weights $\text{w}(v)$, $v \in V$, I want to find a spanning tree $T$ of $G$ with minimum "cost" $\text{w}(T) = \sum_{v\in V} \deg_T(v)\cdot \text{w}(v)$, where $\deg_T(v)$ is the degree of $v$ in $T$.

Can this spanning tree problem be solved efficiently?

• I am afraid that this problem is too elementary for cstheory.stackexchange.com. Spoiler: The problem can be formulated as a special case of the usual minimum spanning tree problem. – Tsuyoshi Ito Feb 5 '13 at 17:50
• Indeed, this problem is a minimum spanning tree problem by defining for each edge $e=uv$, $w'(e)=w(u)+w(v)$; the idea is similar to the answer of the related question cstheory.stackexchange.com/questions/16226/… – user13136 Feb 5 '13 at 20:32
• @Ito and user13136 This is a simple and yet elegant solution! Thank you very much!!! – In Theory Feb 6 '13 at 9:25