Compatibility of unrooted phylogenetic trees is FPT

DOI10.1016/J.TCS.2005.10.033MaRDI QIDQ820142zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• The agreement problem for unrooted phylogenetic trees is FPT
• Fast compatibility testing for rooted phylogenetic trees
• Fast compatibility testing for rooted phylogenetic trees

Cites work

• scientific article; zbMATH DE number 566078 (Why is no real title available?)
• scientific article; zbMATH DE number 1161563 (Why is no real title available?)
• scientific article; zbMATH DE number 1865935 (Why is no real title available?)
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Consensus supertrees: The synthesis of rooted trees containing overlapping sets of labeled leaves
• Easy problems for tree-decomposable graphs
• Extension operations on sets of leaf-labelled trees
• Inferring a Tree from Lowest Common Ancestors with an Application to the Optimization of Relational Expressions
• On the computational power of pushdown automata
• The complexity of reconstructing trees from qualitative characters and subtrees
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs

Cited in

(22)

• Treewidth distance on phylogenetic trees
• Treewidth of display graphs: bounds, brambles and applications
• Finding a maximum compatible tree is NP-hard for sequences and trees
• Compatibility of partitions with trees, hierarchies, and split systems
• Optimizing tree and character compatibility across several phylogenetic trees
• Scanning phylogenetic networks is NP-hard
• On compatibility and incompatibility of collections of unrooted phylogenetic trees
• Snakes and Ladders: A Treewidth Story
• Composing dynamic programming tree-decomposition-based algorithms
• On the quartet distance given partial information
• Maximum parsimony distance on phylogenetic trees: a linear kernel and constant factor approximation algorithm
• The agreement problem for unrooted phylogenetic trees is FPT
• Reduction rules for the maximum parsimony distance on phylogenetic trees
• Fast compatibility testing for rooted phylogenetic trees
• Tree compatibility, incomplete directed perfect phylogeny, and dynamic graph connectivity: an experimental study
• Fast compatibility testing for rooted phylogenetic trees
• Embedding phylogenetic trees in networks of low treewidth
• On the ancestral compatibility of two phylogenetic trees with nested taxa
• Finding a Maximum Compatible Tree for a Bounded Number of Trees with Bounded Degree Is Solvable in Polynomial Time
• Compatibility, incompatibility, tree-width, and forbidden phylogenetic minors
• On low treewidth graphs and supertrees
• Graph triangulations and the compatibility of unrooted phylogenetic trees

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

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