Publication
Acta Informatica
Paper

Optimal α-β trees with capacity constraint

View publication

Abstract

We consider a specific kind of binary trees with weighted edges. Each right edge has weight α while each left edge has weight β. Furthermore, no path in the tree is allowed to contain L or more consecutive α-edges, where L ≧ 1 is fixed. Given, α, β, L and the number of nodes n, an optimal tree is one which minimizes the total weighted path length. Algorithms for constructing an optimal tree as well as all optimal trees for given α, β, L and n are proposed and analyzed. Timing and storage requirements are also discussed. © 1978 Springer-Verlag.

Date

01 Sep 1978

Publication

Acta Informatica

Authors

Share