2026-07-26T02:42:59Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6214 2024-03-06T10:37:47Z ddc:004 open_access

A Duality Based 2-Approximation Algorithm for Maximum Agreement Forest Schalekamp, Frans van Zuylen, Anke van der Ster, Suzanne Maximum agreement forest phylogenetic tree SPR distance subtree prune-and-regraft distance computational biology We give a 2-approximation algorithm for the Maximum Agreement Forest problem on two rooted binary trees. This NP-hard problem has been studied extensively in the past two decades, since it can be used to compute the Subtree Prune-and-Regraft (SPR) distance between two phylogenetic trees. Our result improves on the very recent 2.5-approximation algorithm due to Shi, Feng, You and Wang (2015). Our algorithm is the first approximation algorithm for this problem that uses LP duality in its analysis. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Frans Schalekamp and Anke van Zuylen and Suzanne van der Ster 2016 Is Part Of LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2016.70 urn:nbn:de:0030-drops-62149 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.70 eng https://creativecommons.org/licenses/by/3.0/legalcode