### Abstract

We are given a set script T sign = {T_{1}, T2, . . . , T_{k}) of rooted binary trees, each T_{i} leaf-labeled by a subset ℒ(T_{i}] ⊂ {1,2, . . . , n}. If T is a tree on {1, 2, . . . , n}, we let T\ℒ denote the minimal subtree of T induced by the nodes of ℒ and all their ancestors. The consensus tree problem asks whether there exists a tree T* such that, for every i, T*\ℒ(T_{i}) is homeomorphic to T_{i}. We present algorithms which test if a given sel of trees has a consensus tree and if so. construct one. The deterministic algorithm takes time min{ O (N n^{1/2}), O (N + n^{2} log n)}, where N = ∑_{i} \T_{i}\, and uses linear space. The randomized algorithm takes time O (N log^{3} n) and uses linear space. The previous best for this problem was a 1981 O (N n) algorithm by Aho et al. Our faster deterministic algorithm uses a new efficient algorithm for the following interesting dynamic graph problem: Given a graph G with n nodes and m edges and a sequence of b batches of one or more edge deletions, then, after each batch, either find a new component that has just been created or determine that there is no such component. For this problem, we have a simple algorithm with running time O (n^{2} log n + b_{0} min{n_{2}, m log n}), where b_{0} is the number of batches which do not result in a new component. For our particular application b_{0} ≤ 1. If all edges are deleted, then the best previously known deterministic algorithm requires time O (m √n) to solve this problem. We also present two applications of these consensus tree algorithms which solve other problems in computational evolutionary biology.

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

Pages (from-to) | 1-13 |

Number of pages | 13 |

Journal | Algorithmica (New York) |

Volume | 24 |

Issue number | 1 |

DOIs | |

State | Published - May 1999 |

### Keywords

- Algorithms
- Data structures
- Evolutionary biology
- Theory of databases

### ASJC Scopus subject areas

- Computer Graphics and Computer-Aided Design
- Software
- Safety, Risk, Reliability and Quality
- Applied Mathematics

## Fingerprint Dive into the research topics of 'Constructing a tree from homeomorphic subtrees, with applications to computational evolutionary biology'. Together they form a unique fingerprint.

## Cite this

*Algorithmica (New York)*,

*24*(1), 1-13. https://doi.org/10.1007/PL00009268