---
_id: '11679'
abstract:
- lang: eng
text: "We are given a set T = {T 1 ,T 2 , . . .,T k } of rooted binary trees, each
T i leaf-labeled by a subset L(Ti)⊂{1,2,...,n} . If T is a tree on {1,2, . . .,n
}, we let T|L denote the minimal subtree of T induced by the nodes of L and all
their ancestors. The consensus tree problem asks whether there exists a tree T
* such that, for every i , T∗|L(Ti) is homeomorphic to T i .\r\n\r\nWe present
algorithms which test if a given set 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|Ti| , and uses linear space. The randomized algorithm takes
time O(N log3 n) and uses linear space. The previous best for this problem was
a 1981 O(Nn) 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, b0≤1 . If all edges are deleted, then the best
previously known deterministic algorithm requires time O(mn−−√) to solve this
problem. We also present two applications of these consensus tree algorithms which
solve other problems in computational evolutionary biology."
article_processing_charge: No
article_type: original
author:
- first_name: Monika H
full_name: Henzinger, Monika H
id: 540c9bbd-f2de-11ec-812d-d04a5be85630
last_name: Henzinger
orcid: 0000-0002-5008-6530
- first_name: V.
full_name: King, V.
last_name: King
- first_name: T.
full_name: Warnow, T.
last_name: Warnow
citation:
ama: Henzinger M, King V, Warnow T. Constructing a tree from homeomorphic subtrees,
with applications to computational evolutionary biology. *Algorithmica*.
1999;24:1-13. doi:10.1007/pl00009268
apa: Henzinger, M., King, V., & Warnow, T. (1999). Constructing a tree from
homeomorphic subtrees, with applications to computational evolutionary biology.
*Algorithmica*. Springer Nature. https://doi.org/10.1007/pl00009268
chicago: Henzinger, Monika, V. King, and T. Warnow. “Constructing a Tree from Homeomorphic
Subtrees, with Applications to Computational Evolutionary Biology.” *Algorithmica*.
Springer Nature, 1999. https://doi.org/10.1007/pl00009268.
ieee: M. Henzinger, V. King, and T. Warnow, “Constructing a tree from homeomorphic
subtrees, with applications to computational evolutionary biology,” *Algorithmica*,
vol. 24. Springer Nature, pp. 1–13, 1999.
ista: Henzinger M, King V, Warnow T. 1999. Constructing a tree from homeomorphic
subtrees, with applications to computational evolutionary biology. Algorithmica.
24, 1–13.
mla: Henzinger, Monika, et al. “Constructing a Tree from Homeomorphic Subtrees,
with Applications to Computational Evolutionary Biology.” *Algorithmica*,
vol. 24, Springer Nature, 1999, pp. 1–13, doi:10.1007/pl00009268.
short: M. Henzinger, V. King, T. Warnow, Algorithmica 24 (1999) 1–13.
date_created: 2022-07-27T15:02:28Z
date_published: 1999-05-01T00:00:00Z
date_updated: 2024-11-04T11:41:23Z
day: '01'
doi: 10.1007/pl00009268
extern: '1'
intvolume: ' 24'
keyword:
- Algorithms
- Data structures
- Evolutionary biology
- Theory of databases
language:
- iso: eng
month: '05'
oa_version: None
page: 1-13
publication: Algorithmica
publication_identifier:
eissn:
- 1432-0541
issn:
- 0178-4617
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
related_material:
record:
- id: '11927'
relation: earlier_version
status: public
scopus_import: '1'
status: public
title: Constructing a tree from homeomorphic subtrees, with applications to computational
evolutionary biology
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 24
year: '1999'
...