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

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

Cited in

(33)

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