3 edited tags
| link
2 added 10 characters in body
source | link

Given a directed graph G=(V,E)$G=(V,E)$ and a node r∈V$r\in V$, I need to grow a tree T$T$ rooted at r$r$ that has a minimum weight and spans all reachable nodes in G$G$.

The weight function assigns a non-negative weight to aeach node and, which depends on the node's antecedentsancestors in T$T$. More precisely Specifically, I havefor some fixed sets of nodes S1,S2,...$S_1, S_2, \dots, S_k \subseteq V$,Sk and my the weight function simply returns in how many different sets,of node $v$ is the number of sets $S_i$ that I consider adding to Tcontain $v$ and all of its antecedentsancestors in T reside$T$. 

Any suggestion how to approach this problem?

Given a directed graph G=(V,E) and a node r∈V, I need to grow a tree T rooted at r that has a minimum weight and spans all reachable nodes in G.

The weight function assigns a non-negative weight to a node and depends on node's antecedents in T. More precisely, I have some sets of nodes S1,S2,...,Sk and my weight function simply returns in how many different sets, node that I consider adding to T and all of its antecedents in T reside. Any suggestion how to approach this problem?

Given a directed graph $G=(V,E)$ and a node $r\in V$, I need to grow a tree $T$ rooted at $r$ that has a minimum weight and spans all reachable nodes in $G$.

The weight function assigns a non-negative weight to each node, which depends on the node's ancestors in $T$. Specifically, for some fixed sets of nodes $S_1, S_2, \dots, S_k \subseteq V$, the weight of node $v$ is the number of sets $S_i$ that contain $v$ and all its ancestors in $T$. 

Any suggestion how to approach this problem?

    Tweeted twitter.com/#!/StackCompSci/status/245764352999829504
1
source | link

Minimum vertex-weight directed spanning tree where the weight function depends on the tree

Given a directed graph G=(V,E) and a node r∈V, I need to grow a tree T rooted at r that has a minimum weight and spans all reachable nodes in G.

The weight function assigns a non-negative weight to a node and depends on node's antecedents in T. More precisely, I have some sets of nodes S1,S2,...,Sk and my weight function simply returns in how many different sets, node that I consider adding to T and all of its antecedents in T reside. Any suggestion how to approach this problem?