Balanced Randomized Tree Splitting with Applications to
Evolutionary Tree Constructions
Ming-Yang Kao, Andrzej Lingas, and Anna Ístlin
In Proc. 16th Annual Symposium on Theoretical Aspects of Computer
Science, volume 1563 of Lecture Notes in Computer Science,
pages 184-196. Springer Verlag, Berlin, 1999.
We present a new
technique called balanced randomized tree splitting.
It is useful in constructing unknown trees recursively.
By applying it we obtain two new results on efficient
construction of evolutionary trees:
a new upper time-bound on the problem of constructing an evolutionary
tree from experiments, and a relatively fast
approximation algorithm for the maximum agreement subtree
problem for binary trees for which the maximum number of
leaves in an optimal solution is large.
We also present new lower bounds for the problem of constructing an
evolutionary tree from experiments and for the problem of constructing
a tree from an ultrametric distance matrix.