An improved bound on the Maximum Agreement Subtree problem

2009/03/19 by Szekely, Laszlo, Steel, Mike
#FOS: Biological sciences #Populations and Evolution (q-bio.PE) #Quantitative Methods (q-bio.QM)

paper · doi:10.48550/arxiv.0903.3386

Abstract

We improve the lower bound on the extremal version of the Maximum Agreement Subtree problem. Namely we prove that two binary trees on the same n leaves have subtrees with the same ≥ cloglog n leaves which are homeomorphic, such that homeomorphism is identity on the leaves.

Related

• On the Extremal Maximum Agreement Subtree Problem
• The maximum agreement subtree problem
• On Agreement Subtrees in Multiple Phylogenetic Trees
• Maximum Agreement Subtrees and Hölder homeomorphisms between Brownian trees
• A Duality Based 2-Approximation Algorithm for Maximum Agreement Forest