Optimal parallel algorithms for constructing and maintaining a balanced m-way search tree
type: Item
instance of: scholarly article
title: Optimal parallel algorithms for constructing and maintaining a balanced m-way search tree
zbMATH Open document ID: 0638.68059
DOI: 10.1007/BF01407411
author: Eliezer Dekel
author: Shietung Peng
author: S. Sitharma Iyenga
published in: International Journal of Parallel Programming
publication date: 1986-01-01T00:00:00Z
review text: We present parallel algorithms for constructing and maintaining balanced m-way search trees. These parallel algorithms have time complexity O(1) for an n processors configuration. The formal correctness of the algorithms is given in detail.
Mathematics Subject Classification ID: 68P10
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 4041285
zbMATH Keywords: MIMD
zbMATH Keywords: parallel algorithms
zbMATH Keywords: search trees
MaRDI profile type: Publication
cites work: Q4057549
cites work: Q4195901
cites work: A Generalized Dictionary Machine for VLSI
cites work: Q4190126
cites work: Derivation of a parallel algorithm for balancing binary trees
full work available at URL: https://doi.org/10.1007/bf01407411
OpenAlex ID: W2000376885
Recommended article: Q4738811
Recommended article: A Maximally Parallel Balancing Algorithm for Obtaining Complete Balanced Binary Trees
Recommended article: A unified approach to the parallel construction of search trees
Recommended article: Q3484355
Recommended article: Parallel Algorithms with Optimal Speedup for Bounded Treewidth
Recommended article: Parallel algorithms with optimal speedup for bounded treewidth
Recommended article: Parallel construction of binary trees with near optimal weighted path length
Recommended article: Derivation of a parallel algorithm for balancing binary trees
Recommended article: Cost-optimal parallel algorithms for constructing B-trees
Recommended article: On a sublinear time parallel construction of optimal binary search trees
description: scientific article; zbMATH DE number 4041285