Decompositions of leaf-colored binary trees

DOI10.1006/AAMA.1993.1001MaRDI QIDQ1802339zbMATH OpenOpenAlexFDO

Authors Mike Steel

Publication date 28 November 1993

Published in Advances in Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1006/aama.1993.1001

zbMATH Keywords

binary treescut of treesdecompositionevolutionary treeMenger's theorem

Mathematics Subject Classification ID

Trees (05C05) Coloring of graphs and hypergraphs (05C15) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Problems related to evolution (92D15)

Review text

Evolutionary trees (e.g. leaf-colored binary trees) arise in biomathematics. The evaluation of different heuristics for the NP-hard most parsimonious evolutionary tree problem requires statistics on different numerical parameters of evolutionary trees having fixed pre- colored leaf-set. This research has already been done by an earlier paper of the author [Discrete Appl. Math. 41, No. 3, 245-261 (1993; see the review above)] for 2-colored trees. This paper is aimed to extend that study to multicolored trees. As a possible first step to approach the desired statistics, the author proved enumerative results on special classes of evolutionary trees with 3 or more colors. The fundamental decomposition theorems are based on Menger's theorem and its generalization, see \textit{P. L. Erdős} and \textit{L. A. Székely} [Adv. Appl. Math. 13, No. 4, 375-389 (1992; Zbl 0773.05047)].

Recommendations

• scientific article; zbMATH DE number 1743822
• On the Distribution of Lengths of Evolutionary Trees
• Counting bichromatic evolutionary trees
• Distributions on bicoloured binary trees arising from the principle of parsimony
• The Length of a Leaf Coloration on a Random Binary Tree

Cited in

(7)

• Counting bichromatic evolutionary trees
• On weighted multiway cuts in trees
• Links between maximum likelihood and maximum parsimony under a simple model of site substitution
• Evolutionary trees: An integer multicommodity max-flow -- min-cut theorem
• Combinatorial and algebraic enumeration: a survey of the work of Ian P. Goulden and David M. Jackson
• On non-trivially decomposable types
• scientific article; zbMATH DE number 1743822 (Why is no real title available?)

This page was built for publication: Decompositions of leaf-colored binary trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1802339)