ON the MAXIMUM AGREEMENT SUBTREE CONJECTURE for BALANCED TREES

Magnus Bordewich, Simone Linz, Megan Owen, Katherine S.T. John, Charles Semple, Kristina Wicke

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

Abstract

We give a counterexample to the conjecture of Martin and Thatte that two balanced rooted binary leaf-labeled trees on n leaves have a maximum agreement subtree (MAST) of size at 1 least n2 . In particular, we show that for any c > 0, there exist two balanced rooted binary leaf-labeled trees on n leaves such that any MAST for these two trees has size less than cn2 . We also 1 improve the lower bound of the size of such a MAST to n6 . 1.

Original languageEnglish (US)
Pages (from-to)336-354
Number of pages19
JournalSIAM Journal on Discrete Mathematics
Volume36
Issue number1
DOIs
StatePublished - 2022
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • General Mathematics

Keywords

  • balanced tree
  • catepillar
  • maximum agreement subtree
  • phylogenetic tree

Fingerprint

Dive into the research topics of 'ON the MAXIMUM AGREEMENT SUBTREE CONJECTURE for BALANCED TREES'. Together they form a unique fingerprint.

Cite this