Parallelization of Boruvka's Algorithm

Question

How would I go about parallelizing Boruvka's MST algorithm? I understand that I could find the minimum edge for each node at the same time but how do I guarantee that the nodes selected in parallel are disjoint so that the algorithm works correctly?

Answer 1

I think the parallelization you can use decreases as the algorithm runs.

You may try to parallelize the search for the lightest node of each component and leave to a single machine the union part of the algorithm. The single machine will distribute the components to each sub-machine