Institut für Informatik   Abteilung V

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