Split-or-decompose: improved FPT branching algorithms for maximum agreement forests

DOI10.1016/J.JCSS.2026.103800MaRDI QIDQ7262362zbMATH OpenFDO

Authors David Mestel, Steven Chaplick, Steven Kelk, Ruben Meuwese

Publication date 11 June 2026

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.JCSS.2026.103800

zbMATH Keywords

branching algorithmsfixed parameter tractabilitymaximum agreement forestphylogenetics

Mathematics Subject Classification ID

Computer science (68-XX)

Cites work

• A 3-approximation algorithm for the subtree distance between phylogenies
• A faster FPT algorithm for the maximum agreement forest problem
• A parameterized algorithm for the maximum agreement forest problem on multiple rooted multifurcating trees
• Agreement forests of caterpillar trees: complexity, kernelization and branching
• Better practical algorithms for rSPR distance and hybridization number
• Computing maximum agreement forests without cluster partitioning is folly
• Computing the minimum number of hybridization events for a consistent evolutionary history
• Faster exact computation of rSPR distance
• Fixed-parameter algorithms for maximum agreement forests
• On the complexity of comparing evolutionary trees
• On the computational complexity of the rooted subtree prune and regraft distance
• Parameterized and approximation algorithms for maximum agreement forest in multifurcating trees
• Reflections on kernelizing and computing unrooted agreement forests
• Subtree transfer operations and their induced metrics on evolutionary trees

This page was built for publication: Split-or-decompose: improved FPT branching algorithms for maximum agreement forests

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