A NOTE ON THE EXPECTED PATH-LENGTH OF TREES WITH KNOWN FRINGE

Authors
DEPRISCO R PARLATI G PERSIANO G
Citation
R. Deprisco et al., A NOTE ON THE EXPECTED PATH-LENGTH OF TREES WITH KNOWN FRINGE, Information processing letters, 59(6), 1996, pp. 309-315
Citations number
9
Categorie Soggetti
Information Science & Library Science","Computer Science Information Systems
Journal title
Information processing letters → ACNP
ISSN journal
00200190
Volume
59
Issue
6
Year of publication
1996
Pages
309 - 315
Database
ISI
SICI code
0020-0190(1996)59:6<309:ANOTEP>2.0.ZU;2-T
Abstract
The path length of a tree, that is, the sum of the lengths of all root -leaf paths, is an important measure of efficiency of the tree. The fr inge of a tree is the difference between the lengths of the longest pa th and the shortest path in the tree. The minimal and the maximal path length of trees with N leaves and given fringe have been well studied . In this paper, we initiate the study of the expected path length of the class of trees with N leaves and fringe Delta by giving a closed e xpression for the expected path length when Delta = 2.