Home

Minimal Path Length of Trees with Known Fringe

Roberto De Prisco; Giuseppe Parlati; Giuseppe Persiano

Title:
Minimal Path Length of Trees with Known Fringe
Author(s):
De Prisco, Roberto
Parlati, Giuseppe
Persiano, Giuseppe
Date:
Type:
Technical reports
Department:
Computer Science
Permanent URL:
Series:
Columbia University Computer Science Technical Reports
Part Number:
CUCS-033-93
Abstract:
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.
Subject(s):
Computer science
Item views:
58
Metadata:
text | xml

In Partnership with the Center for Digital Research and Scholarship at Columbia University Libraries/Information Services | Terms of Use