CODEWITHSUNDEEP
algorithmparallel-processinggraph-algorithm
user1804002
user1804002

Reputation:

Minimum spanning tree algorithm in parallel

I know some minimum spanning tree algorithms: Boruvka, Prim and Kruskal. Which of them can be implemented in parallel fashion?

Thanks!

Upvotes: 9

Views: 2185

Answers (1)

Evgeny Kluev
Evgeny Kluev

Reputation: 24647

Out of these 3 algorithms, only Boruvka algorithm might be easily parallelized.

Quotation from the description of Boruvka algorithm on algoritmy.net:

A significant advantage of the Borůvka's algorithm is that is might be easily parallelized, because the choice of the cheapest outgoing edge for each component is completely independent of the choices made by other components.

Upvotes: 4

Related Questions