1993 Reports

Minimal Path Length of Trees with Known Fringe

De Prisco, Roberto; Parlati, Giuseppe; Persiano, Giuseppe

In this paper we continue the study of the path length of trees with known fringe as initiated by [1] and [2]. We compute the path length of the minimal tree with given number of leaves N and fringe ∆ for the case ∆ ≥ N/2. This complements the result of [2] that studied the case ∆ ≤ N/2. Our methods also yields a linear time algorithm for constructing the minimal tree when ∆ ≥ N/2.