Live Webcast 15th Annual Charm++ Workshop

Parallel Prim’s algorithm on dense graphs with a novel extension
PPL Technical Report 2007
Publication Type: Paper
Repository URL:
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.
Research Areas