Minimal Path Length of Trees with Known Fringe
- Minimal Path Length of Trees with Known Fringe
- De Prisco, Roberto
- Computer Science
- Persistent URL:
- Columbia University Computer Science Technical Reports
- Part Number:
- Department of Computer Science, Columbia University
- Publisher Location:
- New York
- In this paper we continue the study of the path length of trees with known fringe as initiated by  and . 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  that studied the case ∆ ≤ N/2. Our methods also yields a linear time algorithm for constructing the minimal tree when ∆ ≥ N/2.
- Computer science
- Item views
text | xml
- Suggested Citation:
- Roberto De Prisco, Giuseppe Parlati, Giuseppe Persiano, 1993, Minimal Path Length of Trees with Known Fringe, Columbia University Academic Commons, https://doi.org/10.7916/D8M61TCX.