Name
Abstract | ||
|---|---|---|
We present parallel algorithms to construct binary trees with almost optimal weighted path length. Specifically, assuming that weights are normalized (to sum up to one) and error refers to the (absolute) difference between the weighted path length of a given tree and the optimal tree with the same weights, we present anO (logn)-time andn(log lognl logn)-EREW-processor algorithm which constructs a tree with error less than 0.18, andO (k logn log*n)-time andn-CREW-processor algorithm which produces a tree with error at most l/nk, and anO (k2 logn)-time andn2-CREW-processor algorithm which produces a tree with error at most l/nk. As well, we describe two sequential algorithms, anO(kn)-time algorithm which produces a tree with error at most l/nk, and anO(kn)-time algorithm which produces a tree with error at most
<img src="/fulltext-image.asp?format=htmlnonpaginated&src=R08QV06177H44471_html\453_2005_Article_BF01941687_TeX2GIFIE1.gif" border="0" alt="
$$1/2^{n2^k }$$
" />. The last two algorithms use different computation models. |
Year | DOI | Venue |
|---|---|---|
1996 | 10.1007/BF01941687 | Algorithmica |
Keywords | Field | DocType |
Huffman trees,Near optimal trees,Optimal trees,Parallel algorithms,PRAM,Prefix codes | Discrete mathematics,Combinatorics,Range tree,Tree traversal,AVL tree,K-ary tree,Optimal binary search tree,Binary tree,Random binary tree,Mathematics,Interval tree | Journal |
Volume | Issue | ISSN |
15 | 2 | 0178-4617 |
Citations | PageRank | References |
6 | 0.61 | 8 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| David G. Kirkpatrick | 1 | 2394 | 541.05 |
| Teresa M. Przytycka | 2 | 775 | 61.98 |