Practical parallel algorithms for minimum spanning trees

We study parallel algorithms for computing the minimum spanning tree of a weighted undirected graph G with n vertices and m edges. We consider an input graph G with m/n/spl ges/p, where p is the number of processors. For this case, we show that simple algorithms with data-independent communication p...

Full description

Saved in:
Bibliographic Details
Main Authors: Dehne, F., Gotz, S.
Format: Conference Proceeding
Language:English
Subjects:
Algorithm design and analysis
Computational modeling
Computer science
Concurrent computing
Costs
Distributed computing
Parallel algorithms
Parallel machines
Tree graphs
User-generated content
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We study parallel algorithms for computing the minimum spanning tree of a weighted undirected graph G with n vertices and m edges. We consider an input graph G with m/n/spl ges/p, where p is the number of processors. For this case, we show that simple algorithms with data-independent communication patterns are efficient both in theory and in practice. The algorithms are evaluated theoretically using Valiant's (1990) BSP model of parallel computation and empirically through implementation results.
ISSN:1060-9857
2575-8462
DOI:10.1109/RELDIS.1998.740525