Live Webcast 15th Annual Charm++ Workshop

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.