Cole, Richard ; Farach-Colton, Martin ; Hariharan, Ramesh ; Przytycka, Teresa ; Thorup, Mikkel
(2000)
*An On(log n) algorithm for the maximum agreement subtree problem for binary trees*
SIAM Journal on Computing, 30
(5).
pp. 1385-1404.
ISSN 0097-5397

Full text not available from this repository.

Official URL: http://epubs.siam.org/doi/abs/10.1137/S00975397963...

Related URL: http://dx.doi.org/10.1137/S0097539796313477

## Abstract

The maximum agreement subtree problem is the following. Given two rooted trees whose leaves are drawn from the same set of items (e.g. species), find the largest subset of these items so that the portions of the two trees restricted to these items are isomorphic. We consider the case which occurs frequently in practice, i.e. the case when the trees are binary and give an O (nlog n) time algorithm for this problem.

Item Type: | Article |
---|---|

Source: | Copyright of this article belongs to Society for Industrial and Applied Mathematics. |

ID Code: | 102239 |

Deposited On: | 09 Mar 2018 11:20 |

Last Modified: | 09 Mar 2018 11:20 |

Repository Staff Only: item control page