ON the MAXIMUM AGREEMENT SUBTREE CONJECTURE for BALANCED TREES

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

doi:10.1137/20M1379678

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 journal › Article › peer-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 language	English (US)
Pages (from-to)	336-354
Number of pages	19
Journal	SIAM Journal on Discrete Mathematics
Volume	36
Issue number	1
DOIs	https://doi.org/10.1137/20M1379678
State	Published - 2022
Externally published	Yes

All Science Journal Classification (ASJC) codes

General Mathematics

Keywords

balanced tree
catepillar
maximum agreement subtree
phylogenetic tree

Access to Document

10.1137/20M1379678

Cite this

@article{c18a144ab4e340bda04533dd7ece2ca8,

title = "ON the MAXIMUM AGREEMENT SUBTREE CONJECTURE for BALANCED TREES",

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.",

keywords = "balanced tree, catepillar, maximum agreement subtree, phylogenetic tree",

author = "Magnus Bordewich and Simone Linz and Megan Owen and John, \{Katherine S.T.\} and Charles Semple and Kristina Wicke",

note = "Publisher Copyright: {\textcopyright} 2022 Society for Industrial and Applied Mathematics",

year = "2022",

doi = "10.1137/20M1379678",

language = "English (US)",

volume = "36",

pages = "336--354",

journal = "SIAM Journal on Discrete Mathematics",

issn = "0895-4801",

publisher = "Society for Industrial and Applied Mathematics Publications",

number = "1",

}

TY - JOUR

T1 - ON the MAXIMUM AGREEMENT SUBTREE CONJECTURE for BALANCED TREES

AU - Bordewich, Magnus

AU - Linz, Simone

AU - Owen, Megan

AU - John, Katherine S.T.

AU - Semple, Charles

AU - Wicke, Kristina

PY - 2022

Y1 - 2022

N2 - 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.

AB - 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.

KW - balanced tree

KW - catepillar

KW - maximum agreement subtree

KW - phylogenetic tree

UR - https://www.scopus.com/pages/publications/85130574375

UR - https://www.scopus.com/pages/publications/85130574375#tab=citedBy

U2 - 10.1137/20M1379678

DO - 10.1137/20M1379678

M3 - Article

AN - SCOPUS:85130574375

SN - 0895-4801

VL - 36

SP - 336

EP - 354

JO - SIAM Journal on Discrete Mathematics

JF - SIAM Journal on Discrete Mathematics

IS - 1

ER -

ON the MAXIMUM AGREEMENT SUBTREE CONJECTURE for BALANCED TREES

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this