also updated the title as requested
Imran Rauf
• 343
• 1
• 7

# Finding directed maximum subtree of aweight arborescence in an edge-weighted DAG

Let $$G$$ be an edge-weighted DAG with a unique source $$s$$. I am interested in findingThe question is how to find out thea maximum weight subtree ofarborescence in $$G$$ rooted at $$s$$.

When all edge weights are positive then the required treearborescence is also spanning and so we can use the directed minimum spanning tree algorithm (http://www.ce.rit.edu/~sjyeec/dmst.html)

What if negative weights are allowed?

Imran Rauf
• 343
• 1
• 7

# Finding directed maximum subtree of a DAG

Let $$G$$ be an edge-weighted DAG with a unique source $$s$$. I am interested in finding out the maximum weight subtree of $$G$$ rooted at $$s$$.

When all edge weights are positive then the required tree is also spanning and so we can use the directed minimum spanning tree algorithm (http://www.ce.rit.edu/~sjyeec/dmst.html)

What if negative weights are allowed?