New reduction rules for the tree bisection and reconnection distance

DOI10.1007/s00026-020-00502-7zbMath1451.05042arXiv1905.01468OpenAlexW2942537438MaRDI QIDQ2210581

Simone Linz, Steven Kelk

Publication date: 7 November 2020

Published in: Annals of Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

generatorphylogenetic treefixed-parameter tractabilityphylogenetic networkkernelizationhybridization numberagreement foresttree bisectiontree reconnection

Mathematics Subject Classification ID

Trees (05C05)

Related Items (4)

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

Cites Work

• Unnamed Item
• On the maximum parsimony distance between phylogenetic trees
• Parameterized and approximation algorithms for maximum agreement forest in multifurcating trees
• On the fixed parameter tractability of agreement-based phylogenetic distances
• 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
• Extremal distances for subtree transfer operations in binary trees
• Fixed-Parameter Algorithms for Maximum Agreement Forests
• Kernelization
• A Tight Kernel for Computing the Tree Bisection and Reconnection Distance between Two Phylogenetic Trees
• 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: New reduction rules for the tree bisection and reconnection distance