### Abstract

Language | English |
---|---|

Pages | 49-66 |

Journal | SIAM Journal on Discrete Mathematics |

Volume | 28 |

Issue number | 1 |

DOIs | |

State | Published - 2014 |

### Cite this

*SIAM Journal on Discrete Mathematics*,

*28*(1), 49-66. DOI: 10.1137/120903567

}

*SIAM Journal on Discrete Mathematics*, vol 28, no. 1, pp. 49-66. DOI: 10.1137/120903567

**Approximation Algorithms for Nonbinary Agreement Forests.** / van Iersel, L.J.J.; Kelk, S.; Lekic, N.; Stougie, L.

Research output: Contribution to journal › Article

TY - JOUR

T1 - Approximation Algorithms for Nonbinary Agreement Forests

AU - van Iersel,L.J.J.

AU - Kelk,S.

AU - Lekic,N.

AU - Stougie,L.

PY - 2014

Y1 - 2014

N2 - Given two rooted phylogenetic trees on the same set of taxa X, the Maximum Agreement Forest (maf) problem asks to find a forest that is, in a certain sense, common to both trees and has a minimum number of components. The Maximum Acyclic Agreement Forest (maaf) problem has the additional restriction that the components of the forest cannot have conflicting ancestral relations in the input trees. There has been considerable interest in the special cases of these problems in which the input trees are required to be binary. However, in practice, phylogenetic trees are rarely binary, due to uncertainty about the precise order of speciation events. Here, we show that the general, nonbinary version of maf has a polynomial-time 4-approximation and a fixedparameter tractable (exact) algorithm that runs in O(4

AB - Given two rooted phylogenetic trees on the same set of taxa X, the Maximum Agreement Forest (maf) problem asks to find a forest that is, in a certain sense, common to both trees and has a minimum number of components. The Maximum Acyclic Agreement Forest (maaf) problem has the additional restriction that the components of the forest cannot have conflicting ancestral relations in the input trees. There has been considerable interest in the special cases of these problems in which the input trees are required to be binary. However, in practice, phylogenetic trees are rarely binary, due to uncertainty about the precise order of speciation events. Here, we show that the general, nonbinary version of maf has a polynomial-time 4-approximation and a fixedparameter tractable (exact) algorithm that runs in O(4

U2 - 10.1137/120903567

DO - 10.1137/120903567

M3 - Article

VL - 28

SP - 49

EP - 66

JO - SIAM Journal on Discrete Mathematics

T2 - SIAM Journal on Discrete Mathematics

JF - SIAM Journal on Discrete Mathematics

SN - 0895-4801

IS - 1

ER -