The arborescence problem is equivalent to the MST problem on strongly connected graphs?

25 Views Asked by At

Consider a strongly connected graph $G=(V,\mathcal{A})$ (if an arc $(i,j)$ in $\mathcal{A}$ then $(j,i)$ in $\mathcal{A}$).

I want to know please if the Rooted Directed MST problem (or the the arborescence) can be solved by using MST algorithms (with weights that are not necessarily symmetric) like Kruskal's or Prim's algorithms since the graph is symmetric.

I think that we can do the following:

1)Neglect the directions and consider the problem as an MST problem.

2)Solve the MST problem.

3)Extract the corrected arcs (or extract the rooted directed tree).

Are these steps correct? Are the two problems equivalent? Is they any reference that handle the problem?

Thank you.