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.



More About This Work

Academic Units
Computer Science
Department of Computer Science, Columbia University
Columbia University Computer Science Technical Reports, CUCS-033-93
Published Here
January 27, 2012