Compatibility of unrooted phylogenetic trees is FPT

DOI10.1016/J.TCS.2005.10.033zbMATH Open1086.68097OpenAlexW2081804360MaRDI QIDQ820142FDOQ820142

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

Recommendations

• The agreement problem for unrooted phylogenetic trees is FPT
• Efficient FPT algorithms for (strict) compatibility of unrooted phylogenetic trees
• Efficient FPT algorithms for (strict) compatibility of unrooted phylogenetic trees
• Fast compatibility testing for rooted phylogenetic trees
• Fast compatibility testing for rooted phylogenetic trees

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (23)

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

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)