### Abstract

The Maximum Agreement Subtree Problem was posed by Finden and Gordon in 1985, and is as follows: given a set S = {S_{1}, S_{2},..., S_{n}} and two trees P and Q leaf-labelled by the elements of S, find a maximum cardinality subset S_{0} of S such that P|S_{0} = Q|S_{0}. This problem arises in evaluationary tree construction, where different methods or data yield (possibly) different trees for the same species on which the trees agree. A superpolynomial time algorithm for finding a maximum agreement subtree of two binary trees was found by Kubicka et al. In this paper, we will present an O(n^{4.5} log n + V) algorithm to determine the largest agreement subtree of two trees on n leaves, where V is the maximum number of nodes in the trees. For the case of trees of maximum degree k, there are two algorithms presented: one has running time O(k!n^{2} + V) while the other has running time O(k^{2.5}n^{2} log n + V). These algorithms also apply when the trees are constrained to be rooted; in this case a maximum agreement subtree is also constrained to be rooted. Each of the algorithms we present can be modified to produce a maximum agreement subtree, rather than computing only the size. Thus, we can solve the searchproblem in the same running time as above.

Original language | English (US) |
---|---|

Pages (from-to) | 77-82 |

Number of pages | 6 |

Journal | Information Processing Letters |

Volume | 48 |

Issue number | 2 |

DOIs | |

State | Published - Nov 8 1993 |

### Keywords

- Algorithms
- Analysis of algorithms
- Combinatorial problems

### ASJC Scopus subject areas

- Computational Theory and Mathematics