Skip to main content

Research Repository

Advanced Search

On the Maximum Agreement Subtree Conjecture for Balanced Trees

Bordewich, Magnus; Linz, Simone; Owen, Megan; St. John, Katherine; Semple, Charles; Wicke, Kristina

On the Maximum Agreement Subtree Conjecture for Balanced Trees Thumbnail


Authors

Simone Linz

Megan Owen

Katherine St. John

Charles Semple

Kristina Wicke



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 .

Citation

Bordewich, M., Linz, S., Owen, M., St. John, K., Semple, C., & Wicke, K. (2022). On the Maximum Agreement Subtree Conjecture for Balanced Trees. SIAM Journal on Discrete Mathematics, 36(1), 336-354. https://doi.org/10.1137/20m1379678

Journal Article Type Article
Acceptance Date Oct 15, 2021
Online Publication Date Jan 31, 2022
Publication Date 2022
Deposit Date Oct 27, 2021
Publicly Available Date Oct 27, 2021
Journal SIAM Journal on Discrete Mathematics
Print ISSN 0895-4801
Electronic ISSN 1095-7146
Publisher Society for Industrial and Applied Mathematics
Peer Reviewed Peer Reviewed
Volume 36
Issue 1
Pages 336-354
DOI https://doi.org/10.1137/20m1379678

Files

Accepted Journal Article (1.3 Mb)
PDF

Copyright Statement
© 2022, Society for Industrial and Applied Mathematics







You might also like



Downloadable Citations