Institut für Informatik
 
Abteilung V

 
Universität Bonn -> Institut für Informatik -> Abteilung V
CS-Reports 2001 Copyright 2001 Universität Bonn, Institut für Informatik, Abt. V
85229

July 4, 2001

Approximating Optimal Binary Trees in Parallel
Piotr Berman, Marek Karpinski and Yakov Nekrich
[Download PostScript] [Download PDF]

In this paper we present new results on an approximate construction of Huffman trees. Our algorithms match asymptotically the time and work needed by known sorting algorithms. For example, we show that an almost-optimal Huffman tree can be constructed in O(log n) time with n processors on a CREW PRAM improving the O(log n log* n) time and n processors result of Kirkpatrick and Przytycka. We also describe an O(n log log n) work algorithm that works on a CRCW PRAM with n/log n processors. This is the first parallel algorithm for the problem with time and work being nearly optimal.

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