2002 · 37 citations · 23 references
ComputingCommunicationComputer ScienceAlgorithmsParallel AlgorithmsParallel ComputingCommunication OverheadData ParallelismGraph AlgorithmsParallel Algorithm DesignCommunication PatternsMinimum Spanning Tree AlgorithmsMinimum Spanning Tree ProblemParallel Graph AlgorithmsParallel Minimum Spanning TreeParallel Minimum Spanning Tree Algorithms
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.
23
A bridging model for parallel computation
Leslie G. Valiant · Communications of the ACM · 1990 · 3.7K citations · Full text
David Culler, Richard M. Karp, David A. Patterson et al. · Communications of the ACM · 1996 · 286 citations · Full text