Reflections on kernelizing and computing unrooted agreement forests
From MaRDI portal
Publication:2069261
DOI10.1007/s10479-021-04352-1zbMath1480.92156arXiv2012.07354OpenAlexW4287553373MaRDI QIDQ2069261
Rim van Wersch, Simone Linz, Steven Kelk, Georgios Stamoulis
Publication date: 20 January 2022
Published in: Annals of Operations Research (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2012.07354
Trees (05C05) Problems related to evolution (92D15) Integer programming (90C10) Distance in graphs (05C12) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (4)
Sharp upper and lower bounds on a restricted class of convex characters ⋮ Convex Characters, Algorithms, and Matchings ⋮ A near-linear kernel for bounded-state parsimony distance ⋮ Deep kernelization for the tree bisection and reconnection (TBR) distance in phylogenetics
Uses Software
Cites Work
- Unnamed Item
- On the maximum parsimony distance between phylogenetic trees
- Kernelizations for the hybridization number problem on multiple nonbinary 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
- A note on convex characters, Fibonacci numbers and exponential-time algorithms
- Experiments on data reduction for optimal domination in networks
- On the complexity of computing MP distance between binary phylogenetic trees
- New reduction rules for the tree bisection and reconnection distance
- The power of linear-time data reduction for maximum matching
- Multilocus phylogenetic analysis with gene tree clustering
- A parsimony-based metric for phylogenetic trees
- Extremal distances for subtree transfer operations in binary trees
- Fixed-Parameter Algorithms for Maximum Agreement Forests
- A Greedy Heuristic for the Set-Covering Problem
- Kernelization
- Computing Maximum Agreement Forests without Cluster Partitioning is Folly
- Engineering Kernelization for Maximum Cut
- Shared-Memory Branch-and-Reduce for Multiterminal Cuts
- A Tight Kernel for Computing the Tree Bisection and Reconnection Distance between Two Phylogenetic Trees
- Parameterized Algorithms
- The probabilities of rooted tree-shapes generated by random bifurcation
- Subtree transfer operations and their induced metrics on evolutionary trees
- On the complexity of comparing evolutionary trees
- What Is Known About Vertex Cover Kernelization?
This page was built for publication: Reflections on kernelizing and computing unrooted agreement forests