Suppose there are an undirected graph $G = (V, E)$ and a function $f : V \rightarrow \mathbb{R}$, which associates a weight for each vertex in $G$. I was wondering if it is possible to find a tree $T = (V, E_T)$, where $E_T \subseteq E$ and $\sum_{i \in V} f(i) d_{i}^T$ is minimal. The root of all trees must be a predetermined node $u \in V$ and $d_i^T$ returns the depth of a node $i$ in the tree $T$.

It looks like a tree with minimum weighted path length problem, which could be built using a Huffman tree, but as it turns out Huffman tree is supposed to be binary, but I would like to find a generic tree, whose the degree of the nodes may be more than two.

Has this problem been classified regarding its complexity?

  • 2
    $\begingroup$ This just seems like a shortest-path tree $\endgroup$ – Alexander - Reinstate Monica Sep 5 '17 at 4:02
  • $\begingroup$ It is a shortest-path tree if $f(i) = 1$ for each $i$, but solving with weighted paths doesn't seem as straightforward as finding a SPT. $\endgroup$ – user12707 Sep 6 '17 at 21:50
  • $\begingroup$ Is f(i) just the edge weight? In that wiki page, they call that dist(u) $\endgroup$ – Alexander - Reinstate Monica Sep 7 '17 at 3:27
  • $\begingroup$ $f(i)$ is the weight of a generic node $i$. It's noteworthy that I'm trying to minimize $\sum_{i \in V} f(i) d_{i}^T$, where $d_i$ is the depth or the distance from the node $i$ to $u$ (the root of the tree). I'm not sure if SPT or MST could solve that problem. $\endgroup$ – user12707 Sep 7 '17 at 21:35
  • $\begingroup$ So if I understand correctly, you just have a weight on each node, and a weight on each edge. You're trying to minimize the sum of node/edge weight products on the path from the start node to every end node. Correct? Couldn't a modified version of Dijkstra's algorithm do this? $\endgroup$ – Alexander - Reinstate Monica Sep 8 '17 at 0:50

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.