Kaikoura tree theorems: Computing the maximum agreement subtree

DOI10.1016/0020-0190(93)90181-8MaRDI QIDQ1313765zbMATH OpenOpenAlexFDO

Authors Mike Steel, Tandy J. Warnow

Publication date 14 August 2000

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(93)90181-8

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05) Graph theory (including graph drawing) in computer science (68R10)

Cites work

• scientific article; zbMATH DE number 434699 (Why is no real title available?)
• An algorithm to find agreement subtrees
• Faster Scaling Algorithms for Network Problems

Cited in

(30)

• Computing the maximum agreement of phylogenetic networks
• On the ancestral compatibility of two phylogenetic trees with nested taxa
• TreeOfTrees method to evaluate the congruence between gene trees
• APPROXIMATING THE MAXIMUM ISOMORPHIC AGREEMENT SUBTREE IS HARD
• An \(O(n\log n)\)-time algorithm for the maximum constrained agreement subtree problem for binary trees
• Bounds on the expected size of the maximum agreement subtree
• Analysis of the Period Recovery Error Bound
• Inducibility in binary trees and crossings in random tanglegrams
• On the Maximum Agreement Subtree Conjecture for Balanced Trees
• From constrained to unconstrained maximum agreement subtree in linear time
• Approximate labelled subtree homeomorphism
• An algebraic view of the relation between largest common subtrees and smallest common supertrees
• On the approximability of the maximum agreement subtree and maximum compatible tree problems
• The asymmetric median tree. --- A new model for building consensus trees
• An improved bound on the maximum agreement subtree problem
• Improved algorithms for maximum agreement and compatible supertrees
• Computing the agreement of trees with bounded degrees
• The agreement metric for labeled binary trees
• Novel phylogenetic network distances based on cherry picking
• Finding a maximum compatible tree is NP-hard for sequences and trees
• On the agreement of many trees
• A duality based 2-approximation algorithm for maximum agreement forest
• Computing the unrooted maximum agreement subtree in sub-quadratic time
• Generalized LCS
• Bounds on the expected size of the maximum agreement subtree for a given tree shape
• On the complexity of comparing evolutionary trees
• An improved algorithm for the maximum agreement subtree problem
• On the extremal maximum agreement subtree problem
• The maximum agreement subtree problem
• Maximum agreement subtrees and Hölder homeomorphisms between Brownian trees

This page was built for publication: Kaikoura tree theorems: Computing the maximum agreement subtree

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