Reduction rules for the maximum parsimony distance on phylogenetic trees

DOI10.1016/j.tcs.2016.07.010zbMath1348.68068arXiv1512.07459OpenAlexW2964224095MaRDI QIDQ306268

Taoyang Wu, Vincent L. Moulton, Mareike Fischer, Steven Kelk

Publication date: 31 August 2016

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

Full work available at URL: https://arxiv.org/abs/1512.07459

zbMATH Keywords

treewidthincongruencefixed parameter tractabilitychainparsimonyphylogenetics

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Problems related to evolution (92D15)

Related Items (7)

Treewidth distance on phylogenetic trees ⋮ A near-linear kernel for bounded-state parsimony distance ⋮ Maximum parsimony distance on phylogenetic trees: a linear kernel and constant factor approximation algorithm ⋮ On compatibility and incompatibility of collections of unrooted phylogenetic trees ⋮ A note on convex characters, Fibonacci numbers and exponential-time algorithms ⋮ Reflections on kernelizing and computing unrooted agreement forests ⋮ A Tight Kernel for Computing the Tree Bisection and Reconnection Distance between Two Phylogenetic Trees

Uses Software

• ComputeTW
• SPRSupertrees

Cites Work

• Unnamed Item
• Unnamed Item
• On the maximum parsimony distance between phylogenetic trees
• Compatibility, incompatibility, tree-width, and forbidden phylogenetic minors
• Fundamentals of parameterized complexity
• Parameterized and approximation algorithms for maximum agreement forest in multifurcating trees
• Compatibility of unrooted phylogenetic trees is FPT
• Treewidth computations. I: Upper bounds
• Graph minors. V. Excluding a planar graph
• Quickly excluding a planar graph
• A parsimony-based metric for phylogenetic trees
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Phylogenetic incongruence through the lens of Monadic Second Order logic
• Excluded Grid Theorem
• On Low Treewidth Graphs and Supertrees
• Easy problems for tree-decomposable graphs
• Subtree transfer operations and their induced metrics on evolutionary trees

This page was built for publication: Reduction rules for the maximum parsimony distance on phylogenetic trees