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

Uniform Generation of Binary Trees in Parallel

โœ Scribed by M.D. Atkinson; J.R. Sack

Publisher
Elsevier Science
Year
1994
Tongue
English
Weight
245 KB
Volume
23
Category
Article
ISSN
0743-7315

No coin nor oath required. For personal study only.

โœฆ Synopsis

An unbiased random generator for binary trees is developed for a CREW-PRAM. The generator is capable of generating a binary tree on (n) nodes in time (O(\log n)), space (O(n)), with (O(n)) processors; it is also capable of generating various related combinatorial objects. O 1994 Academic Press, Inc.

๐Ÿ“œ SIMILAR VOLUMES

On the joint distribution of the nodes i
On the joint distribution of the nodes in uniform multidimensional binary trees
โœ Rainer Kemp ๐Ÿ“‚ Article ๐Ÿ“… 1998 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 313 KB ๐Ÿ‘ 2 views

Multidimensional binary trees represent a symbiosis of trees and tries, and they essentially arise in the construction of search trees for multidimensional keys. The set of nodes in a d-dimensional binary tree can be partitioned into layers according to the nodes appearing in the ith dimension. We d

Link-disjoint embedding of complete bina
Link-disjoint embedding of complete binary trees in meshes
โœ Lee, Sang-Kyu; Choi, Hyeong-Ah ๐Ÿ“‚ Article ๐Ÿ“… 1997 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 342 KB

We consider the problem of embedding complete binary trees into meshes with the objective of minimizing the link congestion. Gibbons and Paterson showed that a complete binary tree T p (with 2 p 0 1 nodes) can be embedded into a 2-dimensional mesh of 2 p nodes with link congestion two. Using the dim

Multiple Templates Access of Trees in Pa
Multiple Templates Access of Trees in Parallel Memory Systems
โœ Vincenzo Auletta; Amelia De Vivo; Vittorio Scarano ๐Ÿ“‚ Article ๐Ÿ“… 1998 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 179 KB

We study the problem of mapping the N nodes of a data structure on M memory modules so that they can be accessed in parallel by templates, i.e., distinct sets of nodes. In literature several algorithms are available for arrays (accessed by rows, columns, diagonals, and subarrays) and trees (accessed