Department of Computer Science
 
Chair V

 
University of Bonn -> Department of Computer Science -> Chair V
CS-Reports 1995 Copyright 1995 University of Bonn, Department of Computer Science, 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 sub-quadratic 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 sub-quadratic work parallel algorithm for construction of an approximately optimal binary search tree in the general case is also given. Sub-quadratic 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 height-limited binary search trees with very small height limitation are presented.

Last Change: 11/05/14 at 09:56:14
 Deutsch
University of Bonn -> Department of Computer Science -> Chair V