also updated the title as requested
Source Link
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?

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?

Finding maximum weight arborescence in an edge-weighted DAG

Let $G$ be an edge-weighted DAG with a unique source $s$. The question is how to find out a maximum weight arborescence in $G$ rooted at $s$.

When all edge weights are positive then the required arborescence 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?

Source Link
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?