Bordewich, Magnus and Linz, Simone and Owen, Megan and St. John, Katherine and Semple, Charles and Wicke, Kristina (2022) 'On the Maximum Agreement Subtree Conjecture for Balanced Trees.', SIAM Journal on Discrete Mathematics, 36 (1). pp. 336-354.
Abstract
We give a counterexample to the conjecture of Martin and Thatte that two balanced rooted binary leaf-labelled trees on n leaves have a maximum agreement subtree (MAST) of size at least n 1 2 . In particular, we show that for any c > 0, there exist two balanced rooted binary leaf-labelled trees on n leaves such that any MAST for these two trees has size less than cn 1 2 . We also improve the lower bound of the size of such a MAST to n 1 6 .
| Item Type: | Article |
|---|---|
| Full text: | (AM) Accepted Manuscript Download PDF (1262Kb) |
| Status: | Peer-reviewed |
| Publisher Web site: | https://doi.org/10.1137/20M1379678 |
| Publisher statement: | © 2022, Society for Industrial and Applied Mathematics |
| Date accepted: | 15 October 2021 |
| Date deposited: | 27 October 2021 |
| Date of first online publication: | 31 January 2022 |
| Date first made open access: | 26 July 2022 |
Save or Share this output
| Export: | |
| Look up in GoogleScholar |
