<p>Let G=(V,E) be a directed weighted graph (not necessarily a tournament) and s be a special node of G so that all nodes in G are reachable from s. The problem is to find a subgraph G'=(V,E') of G so that
(1) G' is a DAG, 
(2) all nodes are reachable from s in G', and 
(3) the sum of the weigh of the arcs in E' is maximal.</p>

<p>Has anyone seen/studied this problem?</p>

CC BY-SA 3.0
2013-08-14T13:54:25.517Z
Are the weights positive?
Vinicius dos Santos
CC BY-SA 3.0
2013-08-16T16:37:15.273Z
Just make a greedy algorithm...taking the maximum weighing remaining edge and add it to the solution if that doesn't violate condition(1).
manasij7479
<graph-theory><graph-algorithms><optimization>
Has anybody studied the problem of finding maximal weighted rooted spanning DAGs?
Antonio
# Has anybody studied the problem of finding maximal weighted rooted spanning DAGs?

(Asked by: username_0 on 2013-08-14)

Let G=(V,E) be a directed weighted graph (not necessarily a tournament) and s be a special node of G so that all nodes in G are reachable from s. The problem is to find a subgraph G'=(V,E') of G so that
(1) G' is a DAG,
(2) all nodes are reachable from s in G', and
(3) the sum of the weigh of the arcs in E' is maximal.

Has anyone seen/studied this problem?

**Tags:** graph-theory, graph-algorithms, optimization

> **Comments:**
> **username_1**: Are the weights positive?  
> **username_2**: Just make a greedy algorithm...taking the maximum weighing remaining edge and add it to the solution if that doesn't violate condition(1).  

---

## 0 answers

