An improved bound on the Maximum Agreement Subtree problem.
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 ≥ c log log n leaves which are homeomorphic, such that homeomorphism is identity on the leaves.
Steel
Mike
M
Biomathematics Research Centre, University of Canterbury, New Zealand, M.Steel@math.canterbury.ac.nz.
Székely
László A
LA