๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

A Randomized Time-Work Optimal Parallel Algorithm for Finding a Minimum Spanning Forest

โœ Scribed by Pettie, Seth; Ramachandran, Vijaya

Book ID
118180381
Publisher
Society for Industrial and Applied Mathematics
Year
2002
Tongue
English
Weight
210 KB
Volume
31
Category
Article
ISSN
0097-5397

No coin nor oath required. For personal study only.

๐Ÿ“œ SIMILAR VOLUMES

Optimal Randomized EREW PRAM Algorithms
Optimal Randomized EREW PRAM Algorithms for Finding Spanning Forests
โœ Shay Halperin; Uri Zwick ๐Ÿ“‚ Article ๐Ÿ“… 2001 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 384 KB

We present the first randomized O log n time and O m + n work EREW PRAM algorithm for finding a spanning forest of an undirected graph G = V E with n vertices and m edges. Our algorithm is optimal with respect to time, work, and space. As a consequence we get optimal randomized EREW PRAM algorithms

A Parallel Algorithm for Computing Minim
A Parallel Algorithm for Computing Minimum Spanning Trees
โœ D.B. Johnson; P. Metaxas ๐Ÿ“‚ Article ๐Ÿ“… 1995 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 840 KB

We present a simple and implementable algorithm that computes a minimum spanning tree of an undirected weighted graph \(G=(V, E)\) of \(n=|V|\) vertices and \(m=|E|\) edges on an EREW PRAM in \(O\left(\log ^{3 / 2} n\right)\) time using \(n+m\) processors. This represents a substantial improvement i