Sign in
Author

Conference

Journal

Organization

Year

DOI
Look for results that meet for the following criteria:
since
equal to
before
between
and
Search in all fields of study
Limit my searches in the following fields of study
Agriculture Science
Arts & Humanities
Biology
Chemistry
Computer Science
Economics & Business
Engineering
Environmental Sciences
Geosciences
Material Science
Mathematics
Medicine
Physics
Social Science
Multidisciplinary
Keywords
(7)
Binary Search
Circuit Design
Data Compression
Data Structure
Group Testing
Linear Time
Weighted Averaging
Related Publications
(1)
Precise minimax redundancy and regret
Subscribe
Academic
Publications
Minimax Trees in Linear Time
Minimax Trees in Linear Time,Computing Research Repository,Pawel Gawrychowski,Travis Gagie
Edit
Minimax Trees in Linear Time
(
Citations: 2
)
BibTex

RIS

RefWorks
Download
Pawel Gawrychowski
,
Travis Gagie
A minimax tree is similar to a Huffman tree except that, instead of minimizing the weighted average of the leaves' depths, it min imizes the maximum of any leaf's weight plus its depth. Golumbic (1976) introduced minimax trees and gave a Huffmanlike, O(nlog n)time al gorithm for building them. Drmota and Szpankowski (2002) gave an other O(nlog n)time algorithm, which checks the Kraft Inequality in each step of a binary search. In this paper we show how Drmota and Szpankowski's algorithm can be made to run in
linear time
on a word RAM with (log n)bit words. We also discuss how our solution applies to problems in data compression,
group testing
and circuit design.
Journal:
Computing Research Repository  CORR
, vol. abs/0812.2, 2008
Cumulative
Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
(
adsabs.harvard.edu
)
(
www.informatik.unitrier.de
)
(
arxiv.org
)
Citation Context
(2)
...More recently Gawrychowski and Gagie [
4
] proposed a different worstcase redundancy problem which also finds its solution in minimizing maximum point wise redundancy, one for which normalization is not relevant and one which assumes all probability distributions are possible (rather than just a subset P←of the probability (simplex)...
J. S. Bhullar
,
et al.
A Huffman Codes Based Approach to Achieve Minimum Redundancy
... set P of possible probability distributions results in a normalized “maximum likelihood distribution.” [16] More recently Gawrychowski and Gagie proposed a different worstcase redundancy problem which also finds its solution in minimizing maximum pointwise redundancy, one for which normalization is not relevant and one which assumes all probability distributions are possible (rather than just a subset P of the probability simplex) [
19
]...
Unknown.
RedundancyRelated Bounds for Generalized
References
(33)
Tight Bounds on Minimum Maximum Pointwise Redundancy
(
Citations: 5
)
Michael B. Baer
Journal:
Computing Research Repository  CORR
, vol. abs/0809.1, 2008
Time Bounds for Selection
(
Citations: 505
)
Manuel Blum
,
Robert W. Floyd
,
Vaughan R. Pratt
,
Ronald L. Rivest
,
Robert Endre Tarjan
Journal:
Journal of Computer and System Sciences  JCSS
, vol. 7, no. 4, pp. 448461, 1973
Alphabetic Minimax Trees of Degree at Most t
(
Citations: 8
)
Don Coppersmith
,
Maria M. Klawe
,
Nicholas Pippenger
Journal:
Siam Journal on Computing  SIAMCOMP
, vol. 15, no. 1, pp. 189192, 1986
Introduction to Algorithms, Second Edition
(
Citations: 12540
)
Thomas H. Cormen
,
Charles E. Leiserson
,
Ronald L. Rivest
,
Clifford Stein
Published in 2001.
Generalized Shannon Code Minimizes the Maximal Redundancy
(
Citations: 10
)
Michael Drmota
,
Wojciech Szpankowski
Conference:
Latin American Theoretical INformatics  LATIN
, pp. 306318, 2002
Sort by:
Citations
(2)
A Huffman Codes Based Approach to Achieve Minimum Redundancy
J. S. Bhullar
,
Parvinder S. Sandhu
,
Manish Gupta
Conference:
International Conference on Computer Modeling and Simulation  ICCMS
, 2010
RedundancyRelated Bounds for Generalized
Unknown