99-15: Addition Chains as Test Trees and a Sequential Variant as the Huffman Problem

DIMACS TR: 99-15

Addition Chains as Test Trees and a Sequential Variant as the Huffman Problem

Author: Julia Abrahams

ABSTRACT
An addition chain can be interpreted as a test tree to identify a single distinguished item from a set of candidates. In this diagnostic problem, there is a constant cost associated with setting up a test, distinct tests distinguish between different size subsets of items, and all tests are set up in advance. If the tests are set up sequentially as needed and if a probability is assigned to each item of its being the single item sought by the testing procedure, the Huffman algorithm finds the optimal test tree in the sense of minimizing the average cost of setting up the tests used in the testing procedure.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1999/99-15.ps.gz

DIMACS Home Page