Rheinische Friedrich-Wilhelms-Universität Bonn Institut für Informatik
 
Abteilung V

 
Universität Bonn -> Institut für Informatik -> Abteilung V
CS-APX-Reports 1995 Copyright 1995 Universität Bonn, Institut für Informatik, Abt. V
8926

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
 English
Universität Bonn -> Institut für Informatik -> Abteilung V

Powered by Zope