1
$\begingroup$

I have a complete graph G which is directed. In essence, a node is connected to all other nodes in the graph. Also, for every pair of nodes, say v and u, there exists two weighted edges one from u tov, and another from v to u.

Under such a configuration for the graph, if I use prim's algorithm, will the algorithm give me an arborescence, which is minimal to the root node, though not to the graph?

I understand that a single run of the prim's algorithm need not give a minimum cost arborescence for the graph. But by finding minimal arborescence by considering each one of the node in graph as root node and then using prim's algorithm, wouldn't this give me the minimum cost aroborescence.

Since the graph G is complete, isn't it guaranteed that an arborescence exist for any given node in G? SO doesn't finding all the minimal cost arborescence for each of the rooted node using prim's and listing them would lead to finding the minimum cost arborescence

I use prim's algorithm as a search procedure for a machine learning structured predction task. So, increase in complexity is not the major concern here for the time being. Using Chu-Liu-Edmond's is not an option under our setting.

Improve this question
$\endgroup$
4
  • 2
    $\begingroup$ Possible duplicate of Why do we have different algorithm for MST when graphs are directed? $\endgroup$
    – Hendrik Jan
    May 9 '17 at 8:21
  • $\begingroup$ Probably the counter examples in the answer to the earlier question can be extended to a complete graph by adding edges with a huge weight? $\endgroup$
    – Hendrik Jan
    May 9 '17 at 8:24
  • $\begingroup$ @HendrikJan - I understand that a single run of prim's can lead to a wrong spanning tree. But What if we can run the algorithm where each node bcomes the root node at successive runs, and then find the best one amongst them. $\endgroup$
    – Amrith Krishna
    May 9 '17 at 9:06
  • 1
    $\begingroup$ Good point, but what if you take the leftmost example from the linked answer and make it into a complete graph by adding edges of weigth 10000? Initial node $u$ probably behaves as before, and the two unnamed nodes do not have a spanning tree if you start there without involving the heavy edges? $\endgroup$
    – Hendrik Jan
    May 9 '17 at 9:28

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.