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?

  • 1
    $\begingroup$ 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. $\endgroup$ – Tsuyoshi Ito Feb 5 '13 at 17:50
  • 7
    $\begingroup$ 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/… $\endgroup$ – user13136 Feb 5 '13 at 20:32
  • $\begingroup$ @Ito and user13136 This is a simple and yet elegant solution! Thank you very much!!! $\endgroup$ – In Theory Feb 6 '13 at 9:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.