I have a weighted DAG and a function computing the weight of edges that is not connected in the DAG. The weight of u to v equals to the weight of v to u.

I want to connect edges to make the DAG a single strongly connected component (any vertex in the new graph can reach any other vertex) with minimum total weights of added edges.

I know that the minimum number of added edges equals to $\text{max}(|source|, |sink|)$ but which vertex connects to which vertex so that the total weights is minimum?

  • $\begingroup$ What are you looking for exactly? Any algorithm? The complexity class of the problem? Approximation results? $\endgroup$ – Peter Taylor Jun 16 '19 at 17:31
  • $\begingroup$ Can you add a url to the original problem? $\endgroup$ – John L. Jun 17 '19 at 2:50
  • $\begingroup$ My problem is similar to this problem codeforces.com/blog/entry/15102. In my problem, the graph needed to be modified is a DAG because I collapased each SCC into a vertex. $\endgroup$ – phqb Jun 17 '19 at 4:51

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.