Technical reports:
Minimal Path Length of Trees with Known Fringe
Roberto De Prisco; Giuseppe Parlati; Giuseppe Persiano
Downloads:
- Title:
- Minimal Path Length of Trees with Known Fringe
- Author(s):
-
De Prisco, Roberto
Parlati, Giuseppe
Persiano, Giuseppe - Date:
- 1993
- Type:
- Technical reports
- Department:
- Computer Science
- Permanent URL:
- http://hdl.handle.net/10022/AC:P:12368
- Series:
- Columbia University Computer Science Technical Reports
- Part Number:
- CUCS-033-93
- Publisher:
- Department of Computer Science, Columbia University
- Publisher Location:
- New York
- 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:
- 33