<p>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$.</p>

<p>Can this spanning tree problem be solved efficiently?</p>

CC BY-SA 3.0
2013-02-05T17:50:26.590Z
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
CC BY-SA 3.0
2013-02-05T20:32:22.843Z
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
http://cstheory.stackexchange.com/questions/16226/finding-a-minimum-node-weight-path
user13136
CC BY-SA 3.0
2013-02-06T09:25:08.877Z
@Ito and user13136 This is a simple and yet elegant solution! Thank you very much!!!
In Theory
<graph-algorithms>
Broadcasting in node-weighted graphs
In Theory
# Broadcasting in node-weighted graphs

(Asked by: username_0 on 2013-02-05)

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?

**Tags:** graph-algorithms

> **Comments:**
> **username_1**: 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.  
> **username_2**: 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 http://cstheory.stackexchange.com/questions/16226/finding-a-minimum-node-weight-path  
> **username_0**: @Ito and username_2 This is a simple and yet elegant solution! Thank you very much!!!  

---

## 0 answers

