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

Optimal parallel construction of heaps

โœ Scribed by C.M. Khoong

Publisher
Elsevier Science
Year
1993
Tongue
English
Weight
242 KB
Volume
48
Category
Article
ISSN
0020-0190

No coin nor oath required. For personal study only.

๐Ÿ“œ SIMILAR VOLUMES

Optimal Parallel Suffix Tree Constructio
Optimal Parallel Suffix Tree Construction
โœ Ramesh Hariharan ๐Ÿ“‚ Article ๐Ÿ“… 1997 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 656 KB

An O(m)-work, O(m)-space, O(log 4 m)-time CREW-PRAM algorithm for constructing the suffix tree of a string s of length m drawn from any fixed alphabet set is obtained. This is the first known work and space optimal parallel algorithm for this problem. It can be generalized to a string s drawn from a

Small-Rank Selection in Parallel, with A
Small-Rank Selection in Parallel, with Applications to Heap Construction
โœ Paul F Dietz; Rajeev Raman ๐Ÿ“‚ Article ๐Ÿ“… 1999 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 115 KB

We study the parallel complexity of selecting the kth smallest of n elements ลฝ on the CRCW PRAM. We show that this problem can be solved in O log log n q . ลฝ. log krlog log n time and O n operations for all 1 F k F nr2, which is superior to existing deterministic bounds when k is small compared to n

Parallel construction of optimal indepen
Parallel construction of optimal independent spanning trees on hypercubes
โœ Jinn-Shyong Yang; Shyue-Ming Tang; Jou-Ming Chang; Yue-Li Wang ๐Ÿ“‚ Article ๐Ÿ“… 2007 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 212 KB

The use of multiple independent spanning trees (ISTs) for data broadcasting in networks provides a number of advantages, including the increase of fault-tolerance and bandwidth. Thus, the designs of multiple ISTs on several classes of networks have been widely investigated. Tang et al. [S.-M. Tang,

A Multiple-Heaps Algorithm for Parallel
A Multiple-Heaps Algorithm for Parallel Simulation of Collision Systems
โœ Mo Mu ๐Ÿ“‚ Article ๐Ÿ“… 2002 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 144 KB

We consider the parallel simulation of collision systems. It has wide application, such as in hard-sphere molecular dynamics simulation for gas dynamics and crystals, as well as in studying molecular collision dynamics of chemical reactions. With detailed analysis, proper data structures are designe