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:
61
Metadata:
text | xml
Suggested Citation:
Roberto De Prisco, Giuseppe Parlati, Giuseppe Persiano, 1993, Minimal Path Length of Trees with Known Fringe, Columbia University Academic Commons, http://hdl.handle.net/10022/AC:P:12368.

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