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?

  • 1
    $\begingroup$ Are the weights positive? $\endgroup$ – Vinicius dos Santos Aug 14 '13 at 13:54
  • $\begingroup$ Just make a greedy algorithm...taking the maximum weighing remaining edge and add it to the solution if that doesn't violate condition(1). $\endgroup$ – manasij7479 Aug 16 '13 at 16:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.