
Universität Bonn > Institut für Informatik > Abteilung V  
CSReports 1995  Copyright 1995 Universität Bonn, Institut für Informatik, Abt. V  
85138

Parallel Subquadratic Work Algorithms for Constructing Approximately Optimal Binary Search Trees
Marek Karpinksi, Lawrence L. Larmore, Wojciech Rytter [Download PostScript] [Download PDF] A sublinear time subquadratic work parallel algorithm for construction of an optimal binary search tree, in a special case of practical interest, namely where the frequencies of items to be stored are not too small, is given. A sublinear time subquadratic work parallel algorithm for construction of an approximately optimal binary search tree in the general case is also given. Subquadratic work and sublinear time are achieved using a fast parallel algorithm for the {\em column minima} problem for Monge matrices developed by Atallah and Kosaraju. The algorithms given in this paper take $O(n^{0.6})$ time with $n$ processors in the CREW PRAM model.A new version of the sequential subquadratic time algorithms for the same problems is also given. New parallel and sequential algorithms for heightlimited binary search trees with very small height limitation are presented. 

Last Change:
11/05/14 at 09:56:14
English 
Universität Bonn > Institut für Informatik > Abteilung V 