A duality based 2-approximation algorithm for maximum agreement forest

DOI10.1007/S10107-022-01790-YOpenAlexW2173511278MaRDI QIDQ2687064

Neil Olver, Anke van Zuylen, Frans Schalekamp, Suzanne Van der Ster, Leen Stougie

Publication date: 1 March 2023

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

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

zbMATH Keywords

computational biologyphylogenetic treemaximum agreement forestSPR distancesubtree prune-and-regraft distance

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Problems related to evolution (92D15) Combinatorial optimization (90C27) Approximation algorithms (68W25)

Related Items (1)

Creating a network-state homomorphism through optimization

Uses Software

• rSPR

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Improved approximation algorithm for maximum agreement forest of two rooted binary phylogenetic trees
• Approximating maximum agreement forest on multiple binary trees
• Approximating the maximum agreement forest on \(k\) trees
• A 3-approximation algorithm for the subtree distance between phylogenies
• The maximum agreement forest problem: Approximation algorithms and computational experiments
• Kaikoura tree theorems: Computing the maximum agreement subtree
• On the computational complexity of the rooted subtree prune and regraft distance
• An Improved Approximation Algorithm for rSPR Distance
• Fixed-Parameter Algorithms for Maximum Agreement Forests
• Fast Algorithms for Finding Nearest Common Ancestors
• A Duality Based 2-Approximation Algorithm for Maximum Agreement Forest
• Approximation Algorithms for Nonbinary Agreement Forests
• Subtree transfer operations and their induced metrics on evolutionary trees
• On the complexity of comparing evolutionary trees

This page was built for publication: A duality based 2-approximation algorithm for maximum agreement forest