3
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • 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
    Commented Feb 5, 2013 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
    Commented Feb 5, 2013 at 20:32
  • $\begingroup$ @Ito and user13136 This is a simple and yet elegant solution! Thank you very much!!! $\endgroup$
    – In Theory
    Commented Feb 6, 2013 at 9:25

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.