Access Restriction

Author Teng, Shang-Hua
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Abstract In this paper, we show that an optimal prefix code (Huffman-equivalent code) over Σ = {0,1,.,σ} for any n letters $a_{1},.,a_{n}$ of frequency $f_{1},.,f_{n}$ can be constructed in $O(log^{2}n)$ time, using only polynomial number of processors. This is done by a uniform reduction of optimal prefix coding problem to a min-plus circuit value problem of polynomial size and linear degree. Thus we can use the parallel circuit evaluation algorithms presented in [7] and [8] to construct a time-efficient and processor-efficient parallel algorithm for optimal prefix coding problem.
Description Affiliation: Univ. of Southern California, Los Angeles (Teng, Shang-Hua)
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 1992-06-30
Publisher Place New York
Journal ACM SIGACT News (SIGA)
Volume Number 18
Issue Number 4
Page Count 8
Starting Page 54
Ending Page 61

Open content in new tab

   Open content in new tab
Source: ACM Digital Library