Parallel Prim’s algorithm on dense graphs with a novel extension

This paper describes parallel implementation of Prim’s algorithm for finding a minimum spanning tree of a dense graph using MPI. Our algorithm uses a novel extension of adding multiple vertices per iteration to achieve significant performance improvements on large problems (up to 200,000 vertices). We describe several experimental results on large graphs illustrating the advantages of our approach on over a thousand processors.

@article{prims07,
    Author = "Ekaterina Gonina and Laxmikant V. Kale",
    Title = "Parallel Prim’s algorithm on dense graphs with a novel extension",
    booktitle = "PPL Technical Report",
    year = 2007,
    month = "October"
}