Cyclic generators and an improved linear kernel for the rooted subtree prune and regraft distance

DOI10.1016/J.IPL.2022.106336MaRDI QIDQ2680228zbMATH OpenOpenAlexFDO

Authors Steven Kelk, Simone Linz, Ruben Meuwese

Publication date 30 January 2023

Published in Information Processing Letters (Search for Journal in Brave)

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

zbMATH Keywords

fixed-parameter tractabilitygraph algorithmskernelizationphylogenetic tree and networksubtree prune and regraft

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• On the computational complexity of the rooted subtree prune and regraft distance
• An improved kernel size for rotation distance in binary trees
• Efficiently inferring pairwise subtree prune-and-regraft adjacencies between phylogenetic trees
• An efficient algorithm for the rooted triplet distance between galled trees
• An algorithm for finding a representation of a subtree distance
• An algorithm for finding a representation of a subtree distance
• Improved methods for computing distances between unordered trees using integer programming
• An improved algorithm for finding a length-constrained maximum-density subtree in a tree
• Refinements to nearest-neighbor searching in k-dimensional trees

Cites work

• A parsimony-based metric for phylogenetic trees
• A quadratic kernel for computing the hybridization number of multiple trees
• A tight kernel for computing the tree bisection and reconnection distance between two phylogenetic trees
• Bounding the number of hybridisation events for a consistent evolutionary history
• Computing the minimum number of hybridization events for a consistent evolutionary history
• Cycle Killer...Qu'est-ce que c'est? On the Comparative Approximability of Hybridization Number and Directed Feedback Vertex Set
• Fixed-parameter algorithms for maximum agreement forests
• Kernelization. Theory of parameterized preprocessing
• Kernelizations for the hybridization number problem on multiple nonbinary trees
• New reduction rules for the tree bisection and reconnection distance
• On the complexity of comparing evolutionary trees
• On the computational complexity of the rooted subtree prune and regraft distance
• On the maximum parsimony distance between phylogenetic trees
• On unrooted and root-uncertain variants of several well-known phylogenetic network problems
• Phylogeny. Discrete and random processes in evolution
• Subtree transfer operations and their induced metrics on evolutionary trees

Cited in

(3)

• On the computational complexity of the rooted subtree prune and regraft distance
• Deep kernelization for the tree bisection and reconnection (TBR) distance in phylogenetics
• A kernel for the maximum agreement forest problem on multiple binary phylogenetic trees

This page was built for publication: Cyclic generators and an improved linear kernel for the rooted subtree prune and regraft distance

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2680228)