Department of Computer Science
 
Chair V

 
University of Bonn -> Department of Computer Science -> Chair V
CS-Reports 2001 Copyright 2001 University of Bonn, Department of Computer Science, 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
 Deutsch
University of Bonn -> Department of Computer Science -> Chair V