×

Average reductions between random tree pairs. (English) Zbl 1309.05158

Summary: There are a number of measures of degrees of similarity between rooted binary trees. Many of these ignore sections of the trees which are in complete agreement. We use computational experiments to investigate the statistical characteristics of such a measure of tree similarity for ordered, rooted, binary trees. We generate the trees used in the experiments iteratively, using the Yule process modeled upon speciation.

MSC:

05C80 Random graphs (graph-theoretic aspects)
05C05 Trees
68R10 Graph theory (including graph drawing) in computer science
68P05 Data structures
PDF BibTeX XML Cite
Full Text: DOI