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?
Has anybody studied the problem of finding maximal weighted rooted spanning DAGs?
graph theory;graph algorithms;optimization