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

Cleary, Sean; Passaro, John; Toruno, Yasser

Involve 8, No. 1, 63-69 (2015).

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

Keywords:

random binary tree pairs