Schalekamp, Frans
[VerfasserIn];
van Zuylen, Anke
[VerfasserIn];
van der Ster, Suzanne
[VerfasserIn]
;
Frans Schalekamp and Anke van Zuylen and Suzanne van der Ster
[MitwirkendeR]
A Duality Based 2-Approximation Algorithm for Maximum Agreement Forest
Anmerkungen:
Diese Datenquelle enthält auch Bestandsnachweise, die nicht zu einem Volltext führen.
Beschreibung:
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.