𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Optimal parallel multiselection on EREW PRAM

✍ Scribed by Hong Shen


Book ID
104304568
Publisher
Elsevier Science
Year
1997
Tongue
English
Weight
409 KB
Volume
23
Category
Article
ISSN
0167-8191

No coin nor oath required. For personal study only.


πŸ“œ SIMILAR VOLUMES


Optimal parallel quicksort on EREW PRAM
✍ Weixiong Zhang; Nageswara S. V. Rao πŸ“‚ Article πŸ“… 1991 πŸ› Springer Netherlands 🌐 English βš– 344 KB
Integer merging on EREW PRAM
✍ Hazem M. Bahig πŸ“‚ Article πŸ“… 2010 πŸ› Springer Vienna 🌐 English βš– 151 KB
Optimal Randomized EREW PRAM Algorithms
✍ 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