Combinatorial Merging

Abstract

Three algorithms are given to construct a weighted r-ary tree with a given set of integer weighted leaves in which the weight of a parent node is 1 + max of its sons. Two goals are of interest; to minimize 1) the weight of the root of the tree, and 2) the number of internal nodes.