Maximum Agreement Subtree in a Set of Evolutionary Trees: Metrics and Efficient Algorithms

DOI10.1137/S0097539794269461zbMATH Open0885.68071MaRDI QIDQ4376196FDOQ4376196

Authors: Amihood Amir, Dmitry Keselman 

Publication date: 10 February 1998

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Recommendations

• Combinatorial Pattern Matching
• Computing the maximum agreement of phylogenetic networks
• Computing the maximum agreement of phylogenetic networks
• An improved algorithm for the maximum agreement subtree problem
• Improved algorithms for maximum agreement and compatible supertrees
• Finding maximal leaf-agreement isomorphic descendent subtrees from phylogenetic trees with different species
• Algorithms and Computation
• Aligning sequences via an evolutionary tree: complexity and approximation
• On the approximability of the maximum agreement subtree and maximum compatible tree problems

zbMATH Keywords

classificationevolutionary treesmaximum agreement subtrees

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Parallel algorithms in computer science (68W10)

Cited In (24)

• APPROXIMATING THE MAXIMUM ISOMORPHIC AGREEMENT SUBTREE IS HARD
• Title not available (Why is that?)
• A constructive algorithm for realizing a distance matrix
• An efficient strategy for generating all descendant subtree patterns from phylogenetic trees with its implementation
• Finding maximal leaf-agreement isomorphic descendent subtrees from phylogenetic trees with different species
• On the Maximum Agreement Subtree Conjecture for Balanced Trees
• Parameterized and approximation algorithms for maximum agreement forest in multifurcating trees
• Fixed-parameter tractability for minimum tree cut/paste distance and minimum common integer partition
• Maximum agreement and compatible supertrees
• Tree edit distance and maximum agreement subtree
• An algebraic view of the relation between largest common subtrees and smallest common supertrees
• Algorithms and Computation
• Finding smallest supertrees under minor containment
• On the approximability of the maximum agreement subtree and maximum compatible tree problems
• Kernelization and parameterized algorithms for covering a tree by a set of stars or paths
• Constructing a consensus phylogeny from a leaf-removal distance (extended abstract)
• Improved algorithms for maximum agreement and compatible supertrees
• Comparison of alignment free string distances for complete genome phylogeny
• Generalized LCS
• On the complexity of comparing evolutionary trees
• On the extremal maximum agreement subtree problem
• An improved algorithm for the maximum agreement subtree problem
• The complexity of comparing multiply-labelled trees by extending phylogenetic-tree metrics
• Computing the maximum agreement of phylogenetic networks

This page was built for publication: Maximum Agreement Subtree in a Set of Evolutionary Trees: Metrics and Efficient Algorithms

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