minimal spanning tree on cuda

Accelerated Computing CUDA CUDA Programming and Performance
1

Hi guys,
I’m intended to implement the minimal spanning tree on cuda
but, i have no ideal which algo is more suitable for development
(prim , kruskal …)
do you guys have any ideal
thank you

Bart99

2

I have a parallel algorithms book that I’ve been looking over for a while, and it says that Sollin’s algorithm is what will probably work best on an architecture like CUDA. Did you ever get around to working on this? I’ve just run into a problem that I’m computing the MST for, and after searching around a bit (and finding nothing), I’ll probably try to implement that algorithm in CUDA to see what kind of speedup I can get from it.

EDIT: I forgot to mention, Sollin’s algorithm is also called Boruvka’s algorithm:

http://en.wikipedia.org/wiki/Bor%C5%AFvka%27s_algorithm

3

could you give the name of the book?

4

It’s Introductions to Parallel Algorithms by C. Xavier and S.S. Iyengar. The ISBN is 0471251828

5

Some of you might have already looked at the paper “Fast minimum spanning tree for large graphs on the GPU” by V. Vineet, P.Harish.
So, it seems that construction of MST on GPU can be done efficiently…?

My problem statement is: Suppose given a graph G, I have constructed a MST T1, after that few edge weights change in the graph G and therefore, it may
result in a different MST T2. Is there a technique to incrementally update the T1 in to T2 when the edge weights on the graph change?

Thanks,
Sh