## Abstract

In computational biology one is often interested in finding the concensus between different evolutionary trees for the same set of species. A popular formalizations is the Maximum Agreement Subtree Problem (MAST) defined as follows: given a set A and two rooted trees T_{0} and T_{1} leaf-labeled by the elements of A, find a maximum cardinality subset B ofA such that the restrictions of T_{0} and T_{1} to B are topologically isomorphic. Polynomial time solutions exist, but they rely on a dynamic program with Θ(n^{2}) nodes-and Θ(n^{2}) running time. We sparsify this dynamic program and show that MAST is equivalent to Unary Weighted Bipartite Matching (UWBM) modulo an O(nc ^{logn}) additive overhead. Applying the best bound for UWBM, we get an O(n^{1. 5}logn) algorithm for MAST. From our sparsification follows an O(nc ^{logn}) time algorithm for the special case of bounded degrees. Also here the best previous bound was Θ(n^{2}).

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

Pages (from-to) | 770-779 |

Number of pages | 10 |

Journal | Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS |

DOIs | |

State | Published - 1994 |

Event | Proceedings of the 35th IEEE Annual Symposium on Foundations of Computer Science - Santa Fe, NM, USA Duration: Nov 20 1994 → Nov 22 1994 |

## ASJC Scopus subject areas

- General Computer Science