Parallel Prim’s algorithm on dense graphs with a novel extension
Authors:
Ekaterina Gonina and Laxmikant Kale
Parallel Programming Laboratory, Department of Computer Science, University
of Illinois at Urbana-Champaign
PPL Technical Report 2007
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.