On the extremal maximum agreement subtree problem

DOI10.1016/J.DAM.2020.07.007MaRDI QIDQ2197478zbMATH OpenOpenAlexFDO

Authors Alexey Markin

Publication date 31 August 2020

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1812.06951

zbMATH Keywords

lower boundphylogenetic treesmaximum agreement subtreelabeled trees

Mathematics Subject Classification ID

Trees (05C05) Extremal problems in graph theory (05C35)

Abstract: Given two phylogenetic trees with the $1,ldots,n$ leaf-set the maximum agreement subtree problem asks what is the maximum size of the subset $Asubseteq1,ldots,n$ such that the two trees are equivalent when restricted to $A$. The long-standing extremal version of this problem focuses on the smallest number of leaves, $mathrmmast(n)$, on which any two (binary and unrooted) phylogenetic trees with $n$ leaves must agree. In this work we prove that this number grows asymptotically as $Theta(logn)$; thus closing the enduring gap between the lower and upper asymptotic bounds on $mathrmmast(n)$.

Recommendations

• The maximum agreement subtree problem
• An improved bound on the maximum agreement subtree problem
• On the approximability of the maximum agreement subtree and maximum compatible tree problems
• Solving the Maximum Agreement SubTree and the Maximum Compatible Tree Problems on Many Bounded Degree Trees
• An improved algorithm for the maximum agreement subtree problem
• On the Maximum Agreement Subtree Conjecture for Balanced Trees
• scientific article; zbMATH DE number 871929
• An \(O(n\log n)\) algorithm for the maximum agreement subtree problem for binary trees
• Polynomial-time algorithms for the ordered maximum agreement subtree problem

Cites work

• scientific article; zbMATH DE number 434699 (Why is no real title available?)
• scientific article; zbMATH DE number 1974592 (Why is no real title available?)
• An \(O(n\log n)\) algorithm for the maximum agreement subtree problem for binary trees
• An improved bound on the maximum agreement subtree problem
• Bounds on the expected size of the maximum agreement subtree
• Bounds on the expected size of the maximum agreement subtree for a given tree shape
• Kaikoura tree theorems: Computing the maximum agreement subtree
• Maximum Agreement Subtree in a Set of Evolutionary Trees: Metrics and Efficient Algorithms
• The maximum agreement subtree problem

Cited in

(8)

• An improved lower bound on the largest common subtree of random leaf-labeled binary trees
• Expected Number of Induced Subtrees Shared by Two Independent Copies of a Random Tree
• An improved bound on the maximum agreement subtree problem
• On the Maximum Agreement Subtree Conjecture for Balanced Trees
• Bounds on the expected size of the maximum agreement subtree
• The maximum agreement subtree problem
• An \(O(n\log n)\) algorithm for the maximum agreement subtree problem for binary trees
• Maximum agreement subtrees and Hölder homeomorphisms between Brownian trees

This page was built for publication: On the extremal maximum agreement subtree problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2197478)