I have to find the minimum spanning tree in a undirected graph, I want to parallelize the code. I read that Boruvka's algorithm is easier to parallelize than Kruskal's or Prim's algorithm. Nevertheless, fast parallel algorithms can be obtained by combining Prim's algorithm with Borůvka's. I don't understand how to combine Prim's algorithm with Boruvka's, could somebody help me? Thank you
1 Answers
1
votes
If you follow wikipedia's link to that claim, you can get to the paper describing it - http://www-static.cc.gatech.edu/~bader/papers/MST-JPDC.pdf
Section 4 described their process, they seem to basically run Prim in parallel from different starting vertices, "compact" each subtree into super-vertices, and rerun recursively until these can no longer be connected.
