×

The size of a maximum agreement subtree for random binary trees. (English) Zbl 1026.92030

Janowitz, M. F. (ed.) et al., Bioconsensus. DIMACS working group meetings on bioconsensus, October 25-26, 2000 and October 2-5, 2001, DIMACS Center. Providence, RI: American Mathematical Society (AMS). DIMACS, Ser. Discrete Math. Theor. Comput. Sci. 61, 55-65 (2003).
Summary: In computational biology, a comrnon way to compare two rooted trees that classify the same set \(L\) of labelled leaves is to determine the largest subset of \(L\) on which the two trees agree. We consider the size of this quantity if one or both trees are generated randomly, according to two simple null models. We obtain analytical bounds, as well as providing some simulation results that suggest a power law similar to the related problem of determining the length of the longest increasing sequence in a random permutation.
For the entire collection see [Zbl 1012.00048].

MSC:

92D15 Problems related to evolution
05C90 Applications of graph theory
05C05 Trees
60J20 Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.)
68R10 Graph theory (including graph drawing) in computer science
PDFBibTeX XMLCite