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

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

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:

could you give the name of the book?

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