Compatibility of unrooted phylogenetic trees is FPT

DOI10.1016/j.tcs.2005.10.033zbMath1086.68097OpenAlexW2081804360MaRDI QIDQ820142

David Bryant, Jens Lagergren

Publication date: 6 April 2006

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2005.10.033

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Related Items (13)

Compatibility of partitions with trees, hierarchies, and split systems ⋮ Reduction rules for the maximum parsimony distance on phylogenetic trees ⋮ Treewidth distance on phylogenetic trees ⋮ Compatibility, incompatibility, tree-width, and forbidden phylogenetic minors ⋮ Efficient FPT algorithms for (strict) compatibility of unrooted phylogenetic trees ⋮ On the quartet distance given partial information ⋮ Graph triangulations and the compatibility of unrooted phylogenetic trees ⋮ Maximum parsimony distance on phylogenetic trees: a linear kernel and constant factor approximation algorithm ⋮ Scanning Phylogenetic Networks Is NP-hard ⋮ On compatibility and incompatibility of collections of unrooted phylogenetic trees ⋮ Fast compatibility testing for rooted phylogenetic trees ⋮ Tree compatibility, incomplete directed perfect phylogeny, and dynamic graph connectivity: an experimental study ⋮ Treewidth of display graphs: bounds, brambles and applications

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Consensus supertrees: The synthesis of rooted trees containing overlapping sets of labeled leaves
• The complexity of reconstructing trees from qualitative characters and subtrees
• Extension operations on sets of leaf-labelled trees
• On the computational power of pushdown automata
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Easy problems for tree-decomposable graphs
• Inferring a Tree from Lowest Common Ancestors with an Application to the Optimization of Relational Expressions
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth

This page was built for publication: Compatibility of unrooted phylogenetic trees is FPT