A Tight Kernel for Computing the Tree Bisection and Reconnection Distance between Two Phylogenetic Trees

DOI10.1137/18M122724XzbMath1430.68130arXiv1811.06892OpenAlexW2901518681WikidataQ127291120 ScholiaQ127291120MaRDI QIDQ5233752

Steven Kelk, Simone Linz

Publication date: 6 September 2019

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

generatorphylogenetic treefixed-parameter tractabilityphylogenetic networkkernelizationhybridization numbertree bisection and reconnection

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Trees (05C05) Problems related to evolution (92D15) Parameterized complexity, tractability and kernelization (68Q27)

Related Items (6)

Cyclic generators and an improved linear kernel for the rooted subtree prune and regraft distance ⋮ A near-linear kernel for bounded-state parsimony distance ⋮ Deep kernelization for the tree bisection and reconnection (TBR) distance in phylogenetics ⋮ New reduction rules for the tree bisection and reconnection distance ⋮ Maximum parsimony distance on phylogenetic trees: a linear kernel and constant factor approximation algorithm ⋮ Reflections on kernelizing and computing unrooted agreement forests

Cites Work

• 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
• Constructing minimal phylogenetic networks from softwired clusters is fixed parameter tractable
• 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
• Computing the minimum number of hybridization events for a consistent evolutionary history
• A parameterized algorithm for the maximum agreement forest problem on multiple rooted multifurcating trees
• On unrooted and root-uncertain variants of several well-known phylogenetic network problems
• On the computational complexity of the rooted subtree prune and regraft distance
• A parsimony-based metric for phylogenetic trees
• A quadratic kernel for computing the hybridization number of multiple trees
• Hybridization Number on Three Rooted Binary Trees is EPT
• Phylogeny
• Fixed-Parameter Algorithms for Maximum Agreement Forests
• Cycle Killer...Qu'est-ce que c'est? On the Comparative Approximability of Hybridization Number and Directed Feedback Vertex Set
• Kernelization Lower Bounds by Cross-Composition
• Parameterized Algorithms
• Subtree transfer operations and their induced metrics on evolutionary trees
• On the complexity of comparing evolutionary trees

This page was built for publication: A Tight Kernel for Computing the Tree Bisection and Reconnection Distance between Two Phylogenetic Trees