Maximum parsimony distance on phylogenetic trees: a linear kernel and constant factor approximation algorithm
From MaRDI portal
Publication:2221808
DOI10.1016/j.jcss.2020.10.003zbMath1477.68133arXiv2004.02298OpenAlexW3111159905MaRDI QIDQ2221808
Publication date: 2 February 2021
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2004.02298
Problems related to evolution (92D15) Approximation algorithms (68W25) Parameterized complexity, tractability and kernelization (68Q27)
Related Items (2)
Convex Characters, Algorithms, and Matchings ⋮ A near-linear kernel for bounded-state parsimony distance
Uses Software
Cites Work
- On the maximum parsimony distance between phylogenetic trees
- Reduction rules for the maximum parsimony distance on phylogenetic trees
- Fundamentals of parameterized complexity
- Parameterized and approximation algorithms for maximum agreement forest in multifurcating trees
- On the fixed parameter tractability of agreement-based phylogenetic distances
- Approximating maximum agreement forest on multiple binary trees
- A note on convex characters, Fibonacci numbers and exponential-time algorithms
- Compatibility of unrooted phylogenetic trees is FPT
- Convex recolorings of strings and trees: Definitions, hardness results and algorithms
- Comparison of phylogenetic trees
- Treewidth distance on phylogenetic trees
- A parameterized algorithm for the maximum agreement forest problem on multiple rooted multifurcating trees
- On the complexity of computing MP distance between binary phylogenetic trees
- Binary Steiner trees: structural results and an exact solution approach
- New reduction rules for the tree bisection and reconnection distance
- A parsimony-based metric for phylogenetic trees
- Efficient FPT algorithms for (strict) compatibility of unrooted phylogenetic trees
- Extremal distances for subtree transfer operations in binary trees
- Phylogenetic incongruence through the lens of Monadic Second Order logic
- Hybridization Number on Three Rooted Binary Trees is EPT
- Phylogeny
- Fixed-Parameter Algorithms for Maximum Agreement Forests
- Computational Phylogenetics
- Treewidth of display graphs: bounds, brambles and applications
- A Tight Kernel for Computing the Tree Bisection and Reconnection Distance between Two Phylogenetic Trees
- Parameterized Algorithms
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- Subtree transfer operations and their induced metrics on evolutionary trees
- Unnamed Item
- Unnamed Item
This page was built for publication: Maximum parsimony distance on phylogenetic trees: a linear kernel and constant factor approximation algorithm
