On the Complexity of Constructing Evolutionary Trees

No abstract is available for this paper.

• Publication year

  1999

• Venue

  Journal of combinatorial optimization

• Publication date

  1999-12-01

• Fields of study

  Biology, Mathematics, Computer Science

• Identifiers
  DOI 10.1023/A:1009833626004
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• New 3⁄4 - Approximation Algorithms for MAX SAT

  2001cited by this paper
• Constructing a Tree from Homeomorphic Subtrees, with

  1999cited by this paper
• Minimum cuts in near-linear time

  1998cited by this paper
• General techniques for comparing unrooted evolutionary trees

  1997cited by this paper
• Approximation Algorithms for NP-Hard Problems

  1997cited by this paper
• Constructing a Tree from Homeomorphic Subtrees, with Applications to Computational Evolutionary Biology

  1996cited by this paper
• On the Complexity of Comparing Evolutionary Trees

  1996cited by this paper
• Testing of the long code and hardness for clique

  1996cited by this paper
• The Asymmetric Median Tree - A New Model for Building Consensus Trees

  1996cited by this paper
• Computing the Unrooted Maximum Agreement Subtree in Sub-quadratic Time

  1996cited by this paper
• Computing the Agreement of Trees with Bounded Degrees

  1995cited by this paper
• Computing the local consensus of trees

  1995cited by this paper
• Optimal evolutionary tree comparison by sparse dynamic programming

  1994cited by this paper
• Fast comparison of evolutionary trees

  1994influential reference
• New 3/4-Approximation Algorithms for the Maximum Satisfiability Problem

  1994cited by this paper
• Maximum agreement subtree in a set of evolutionary trees-metrics and efficient algorithms

  1994cited by this paper
• Kaikoura Tree Theorems: Computing the Maximum Agreement Subtree

  1993cited by this paper
• On the Size of Systems of Sets Every t of Which Have an SDR, with an Application to the Worst-Case Ratio of Heuristics for Packing Problems

  1989cited by this paper
• Obtaining common pruned trees

  1985cited by this paper
• Inferring a Tree from Lowest Common Ancestors with an Application to the Optimization of Relational Expressions

  1981influential reference
• Approximation algorithms for combinatorial problems

  1973cited by this paper

• Learning latent tree models with small query complexity

  2024cites this paper
• Building a Small and Informative Phylogenetic Supertree

  2023cites this paper
• A polynomial time algorithm for finding a minimum 4-partition of a submodular function

  2023cites this paper
• Heuristic algorithms for best match graph editing

  2021cites this paper
• Netcombin: An algorithm for constructing optimal phylogenetic network from rooted triplets

  2020cites this paper
• CBTH: A New Algorithm for Maximum Rooted Triplets Consistency Problem

  2020cites this paper
• The approximability of maximum rooted triplets consistency with fan triplets and forbidden triplets

  2019cites this paper
• Minimal Phylogenetic Supertrees and Local Consensus Trees

  2018cites this paper
• Solving Phylogenetic Network Containment Problems using Cherry-picking Sequences

  2018cites this paper
• Determining the Consistency of Resolved Triplets and Fan Triplets

  2017cites this paper
• The Approximability of Maximum Rooted Triplets Consistency with Fan Triplets and Forbidden Triplets

  2015cites this paper
• Phylogenomics with paralogs

  2015cites this paper
• New Heuristics for Rooted Triplet Consistency

  2013cites this paper
• Resolving Rooted Triplet Inconsistency by Dissolving Multigraphs

  2013cites this paper
• Faster exact computation of rSPR distance

  2013cites this paper
• Computing minimum multiway cuts in hypergraphs

  2013cites this paper
• The Orthology Road Theory and Methods in Orthology Analysis

  2013influential citation
• New Algorithms on Rooted Triplet Consistency

  2012cites this paper
• A N ew H euristic Algorithm for MRTC Problem

  2012cites this paper
• Asymptotic Limits of a New Type of Maximization Recurrence with an Application to Bioinformatics

  2012cites this paper
• FlipCut Supertrees: Towards Matrix Representation Accuracy in Polynomial Time

  2011cites this paper
• Encoding and Constructing 1-Nested Phylogenetic Networks with Trinets

  2011cites this paper
• Kernel and fast algorithm for dense triplet inconsistency

  2010cites this paper
• Computing Minimum Multiway Cuts in Hypergraphs from Hypertree Packings

  2010cites this paper
• The Complexity of Inferring a Minimally Resolved Phylogenetic Supertree

  2010cites this paper
• Divide-and-Conquer Algorithms for Partitioning Hypergraphs and Submodular Systems

  2009cites this paper
• Computing Rooted and Unrooted Maximum Consistent Supertrees

  2009cites this paper
• UNIQUENESS, INTRACTABILITY AND EXACT ALGORITHMS: REFLECTIONS ON LEVEL-K

  2009cites this paper
• New Results on Optimizing Rooted Triplets Consistency

  2008cites this paper
• Maximum Agreement Supertree

  2008cites this paper
• Constructing Level-2 Phylogenetic Networks from Triplets

  2007cites this paper
• Uniqueness, Intractability and Exact Algorithms: Reflections on Level-k Phylogenetic Networks

  2007cites this paper
• Randomized Approximation Algorithms: Facility Location, Phylogenetic Networks, Nash Equilibria

  2007cites this paper
• Algorithms, Haplotypes and Phylogenetic Networks

  2007cites this paper
• Maximum agreement and compatible supertrees

  2007cites this paper
• Worst-case optimal approximation algorithms for maximizing triplet consistency within phylogenetic networks

  2007influential citation
• Inferring phylogenetic relationships avoiding forbidden rooted triplets

  2006influential citation
• Algorithms for combining rooted triplets into a galled phylogenetic network

  2005influential citation
• Constructing the Maximum Consensus Tree from Rooted Triples

  2004cites this paper
• Polynomial-Time Algorithms for the Ordered Maximum Agreement Subtree Problem

  2004cites this paper
• Rooted Maximum Agreement Supertrees

  2004influential citation
• The Maximum Agreement of Two Nested Phylogenetic Networks

  2004cites this paper
• Inferring a Level-1 Phylogenetic Network from a Dense Set of Rooted Triplets

  2004cites this paper
• Computing the Maximum Agreement of Phylogenetic Networks

  2004cites this paper
• Maximum Agreement and Compatible Supertrees (Extended Abstract)

  2004cites this paper
• Consensus Algorithms for Trees and Strings

  2003cites this paper
• On the Complexity of Inferring Rooted Evolutionary Trees

  2001cites this paper
• Efficient Guiding Towards Cost-Optimality in UPPAAL

  2001cites this paper
• Approximating the Maximum Isomorphic Agreement Subtree Is Hard

  2000cites this paper
• Constructing Level-2 Phylogenetic Networks from Triplets

  year unknowncites this paper
• Constructing Level-2 Phylogenetic Networks from Triplets

  year unknowncites this paper
• On the approximation of computing of evolutionary trees Research report-LIRMM 05016

  year unknowncites this paper