search

Algue-Rythme / MST_MPI

Implementing parallel Kruskal and Prim MST algorithms using MPI
0 stars 1 forks source link

Parallel Prim #1

Open DyeKuu opened 4 years ago

DyeKuu commented 4 years ago

Hello, I am wondering if you would like to think about implementing a parallel prim's algorithm by using a min-heap for the priority queue? I have tried but I failed, do you have any idea?

Algue-Rythme commented 4 years ago

Hi, I don't plan on doing that. Parallel implementation of min-heap is challenging. It is a homework I made two years ago (see instructions in projet.pdf) and report in rapport.pdf I cannot guarantee that it is bug free.

I am not sure my implementations are fast. The graph is taken in input as an adjancency matrix, which is awful from complexity point of view. Building this adjacency matrix is the main bottelneck of the algorithm.

If your graph is sparse, you should use the sequential implementations of Prim or Kruskal (the latter should be faster with disjoint set datastructure and quick sort).

If your graph is dense, you should use the parallel Kruskal I provide. But I can not guarantee that it will be faster.

For your usage, I would recommend using the project of somebody else.