No Access

WORK-EFFICIENT ALGORITHMS FOR THE CONSTRUCTION OF LENGTH-LIMITED HUFFMAN CODES

MAREK KARPINSKI

Dept. of Computer Science, University of Bonn, Germany

Work partially supported by a DFG grant, DIMACS, and IST grant 14036 (RAND-APX).

Search for more papers by this author

LAWRENCE LARMORE

School of Computer Science, University of Nevada, Las Vegas, USA

Work partially supported by NSF grant CCR-0312093.

Search for more papers by this author

, and

YAKOV NEKRICH

Dept. of Computer Science, University of Bonn, Germany

Work partially supported by IST grant 14036 (RAND-APX).

Search for more papers by this author

https://doi.org/10.1142/S012962640400174XCited by:0 (Source: Crossref)

Abstract

We present an algorithm for parallel construction of Huffman codes in time with p processors, where p>1, improving the previous result of Levcopoulos and Przytycka. We also show, that a greedy Huffman tree can be constructed in time with n processors.

Keywords:

References

P. Berman, M. Karpinski and Y. Nekrich, Approximating Huffman Codes in Parallel, Proc. 29th ICALP2380 (Springer, 2002) pp. 845–855. Google Scholar
D. A. Huffman, Proc. IRE 40, 1098 (1951), DOI: 10.1109/JRPROC.1952.273898. Crossref, Web of Science, Google Scholar
D. Kirkpatrick and T. Przytycka, Algorithmica 15(2), 172 (1996), DOI: 10.1007/BF01941687. Crossref, Web of Science, Google Scholar
L. Larmore and T. Przytycka, SIAM Journal on Computing 24(6), 1163 (1995), DOI: 10.1137/S0097539792233245. Crossref, Web of Science, Google Scholar
Ch. Levcopoulos and T. Przytycka, Parallel Processing Letters 4(1-2), 37 (1994), DOI: 10.1142/S0129626494000053. Link, Google Scholar
J. van Leeuwen, On the Construction of Huffman Trees, Proc. 3rd ICALP (Edinburgh University Press, 1976) pp. 382–410. Google Scholar