Academic
Publications
Minimax Trees in Linear Time

Minimax Trees in Linear Time,Computing Research Repository,Pawel Gawrychowski,Travis Gagie

Minimax Trees in Linear Time   (Citations: 2)
BibTex | RIS | RefWorks Download
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 Huffman-like, 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.
    • ...More recently Gawrychowski and Gagie [4] proposed a different worst-case 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. Bhullaret 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 worst-case 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. Redundancy-Related Bounds for Generalized

Sort by: