An improved bound on the maximum agreement subtree problem

✍ Scribed by Mike Steel; László A. Székely

• Publisher: Elsevier Science
• Year: 2009
• Tongue: English
• Weight: 299 KB
• Volume: 22
• Category: Article
• ISSN: 0893-9659
• DOI: 10.1016/j.aml.2009.06.019

✦ Synopsis

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.