@inproceedings{15446116ab804372b089d9cf9dd847ca,
title = "Approximating Huffman codes in parallel",
abstract = "In this paper we present new results on the approximate parallel construction of Huffman codes. Our algorithm achieves linear work and logarithmic time, provided that the initial set of elements is sorted. This is the first parallel algorithm for that problem with the optimal time and work. Combining our approach with the best known parallel sorting algorithms we can construct an almost optimal Huffman tree with optimal time and work. This also leads to the first parallel algorithm that constructs exact Huffman codes with maximum codeword length H in time O(H) and with n processors. This represents a useful improvement since most practical situations satisfy H = O(log n).",
author = "Piotr Berman and Marek Karpinski and Yakov Nekrich",
year = "2002",
doi = "10.1007/3-540-45465-9_72",
language = "English (US)",
isbn = "3540438645",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "845--855",
editor = "Peter Widmayer and Stephan Eidenbenz and Francisco Triguero and Rafael Morales and Ricardo Conejo and Matthew Hennessy",
booktitle = "Automata, Languages and Programming - 29th International Colloquium, ICALP 2002, Proceedings",
address = "Germany",
note = "29th International Colloquium on Automata, Languages, and Programming, ICALP 2002 ; Conference date: 08-07-2002 Through 13-07-2002",
}